Leonid Gurvits
- 1.A. Aleksandrov, On the theory of mixed volumes of convex bodies, IV, Mixed discriminants and mixed volumes (in Russian), Mat. $b. (N.S.) 3:227-251, 1938.Google Scholar
- 2.M. Avriel, Nonlinear programming: analysis and methods, Prentice-Hall, 1976.Google Scholar
- 3.I. Barany and Z. Furedi, Computing the volume is difficult, Discrete ~ Computational Geometry, 2:319-326, 1987.Google Scholar
- 4.R. Bapat, Mixed discriminants of positive semidefinite matrices, Linear Algebra and its Applications 126:107- 124, 1989.Google ScholarCross Ref
- 5.A. I. Barvinok, Computing Mixed Discriminants, Mixed Volumes, and Permanents, Discrete ~4 Computational Geometry, 18:205-237 (1997).Google Scholar
- 6.A. I. Barvinok, A simple polynomial time algorithm to approximate permanents and mixed discriminants within a simply exponential factor, Random Structures and Alg., 14:29-61, 1999. Google ScholarDigital Library
- 7.M. Dyer and A. Frieze, The complexity of computing the volume of a polyhedron, SIAM J. Comput., 17:967- 994, 1988. Google ScholarDigital Library
- 8.M. Dyer, P. Gritzmann and A. Hufnagel, On the complexity of computing mixed volumes, SIAM J. Comput., 27(2):356-400, 1998. Google ScholarDigital Library
- 9.J. Edmonds, Submodular functions, matroids, and certain polyhedra, in Combinatorial structures and their applications, R. Guy, H. Hanani, N. Sauer and J. Sch5nheim, eds., Gordon and Breach, New York, 69- 87, 1970.Google Scholar
- 10.G.P. Egorychev, The solution of van der Waerden's problem for permanents, Advances in Math., 42:299- 305, 1981.Google ScholarCross Ref
- 11.D. i. Falikman, Proof of the van der Waerden's conjecture on the permanent of a doubly stochastic matrix, Mat. Zametki 29(6):931-938, 957, 1981, (in Russian).Google Scholar
- 12.S. Friedland, A lower bound for the permanent of a doubly stochastic matrix, Annals of Mathematics, 110:167- 176, 1979.Google ScholarCross Ref
- 13.M. GrStschel~, L. Lovasz and A. Schrijver, Geometric Algorithms and Uombinatorial Optimization, Springer- Verlag, Berlin, 1988.Google Scholar
- 14.L. Gurvits, Proving Generalized van der Waerden Conjecture - A proof of Bapat's conjecture on mixed discriminants, preprint, 1999.Google Scholar
- 15.M. Jerrum and A. Sinclair, Approximating the permanent, SIAM J. Comput., 18:1149-1178, 1989. Google ScholarDigital Library
- 16.F. John, Extremum problems with inequalities as subsidiaxy conditions, Studies and Essays, presented to R. Courant on his 60th birthday, Interscience, New York, 1948.Google Scholar
- 17.N. Karmarkar, R. Karp, R. Lipton, L. Lovasz and M. Luby, A Monte-Carlo algorithm for estimating the permanent, SIAM J. Comput., 22(2):284-293, 1993. Google ScholarDigital Library
- 18.N. Linial, A. Samorodnitsky and A. Wigderson, A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, Proc. 30 A CM Syrup. on Theory of Computing, ACM, New York, 1998. Google ScholarDigital Library
- 19.Y. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming, SIAM, Philadelphia, PA, 1994.Google Scholar
- 20.A. Panov, On mixed discriminants connected with positive semidefinite quadratic forms, Soviet Math. Dokl. 31 (1985).Google Scholar
- 21.R. Schneider, Convex bodies: The Brunn-Minkowski Theory, Encyclopedia of Mathematics and Its Applications, vol. 44, Cambridge University Press, New York, 1993.Google Scholar
- 22.L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science, 8(2):189-201, 1979.Google Scholar
Index Terms
- A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume
Recommendations
Irrational Mixed Decomposition and Sharp Fewnomial Bounds for Tropical Polynomial Systems
Given convex polytopes $$P_1,\ldots ,P_r \subset \mathbb {R}^n$$P1, ,Pr Rn and finite subsets $$\mathcal {W}_I$$WI of the Minkowski sums $$P_I=\sum _{i \in I} P_i$$PI= i IPi, we consider the quantity $$N(\mathbf {W})=\sum _{I \subset \mathbf{[}r \mathbf{...
A Polynomial-Time Algorithm to Approximate the Mixed Volume within a Simply Exponential Factor
Let K=(K1,ź,Kn) be an n-tuple of convex compact subsets in the Euclidean space Rn, and let V(ź) be the Euclidean volume in Rn. The Minkowski polynomial VK is defined as VK(ź1,ź,źn)=V(ź1K1+źźź+źnKn) and the mixed volume V(K1,ź,Kn) as $$V(K_{1},\ldots,K_{...
Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions
We present a deterministic algorithm for finding the significant Fourier frequencies of a given signal $f\in\BBC^{N}$ and their approximate Fourier coefficients in running time and sample complexity polynomial in $\log N$, $L_{1}(\widehat f)/\Vert\...
Comments