✦ LIBER ✦

A Polynomial-Time Algorithm to Approximate the Mixed Volume within a Simply Exponential Factor

✍ Scribed by Leonid Gurvits

Book ID: 106149922
Publisher: Springer
Year: 2009
Tongue: English
Weight: 427 KB
Volume: 41
Category: Article
ISSN: 0179-5376
DOI: 10.1007/s00454-009-9147-5

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Polynomial Time Algorithms to Approximat

Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor

✍ Alexander Barvinok 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB

We present real, complex, and quaternionic versions of a simple randomized polynomial time algorithm to approximate the permanent of a nonnegative matrix and, more generally, the mixed discriminant of positive semidefinite matrices. The algorithm provides an unbiased estimator, which, with high prob

A random polynomial-time algorithm for a

A random polynomial-time algorithm for approximating the volume of convex bodies

✍ Dyer, Martin; Frieze, Alan; Kannan, Ravi 📂 Article 📅 1991 🏛 Association for Computing Machinery 🌐 English ⚖ 967 KB

A polynomial-time algorithm to approxima

A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant

✍ Mary Cryan; Martin Dyer 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 232 KB

We consider the problem of counting the number of contingency tables with given row and column sums. This problem is known to be #P-complete, even when there are only two rows (Random Structures Algorithms 10(4) (1997) 487). In this paper we present the first fully polynomial randomized approximatio