A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume

Full text

Pdf (884 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents

Portland, Oregon, United States

Pages: 48 - 57

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Leonid Gurvits	NECI, Princeton
Alex Samorodnitsky	Institute for Advanced Study and DIMACS

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 26, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/335305.335311 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	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.
	2	M. Avriel, Nonlinear programming: analysis and methods, Prentice-Hall, 1976.
	3	I. Barany and Z. Furedi, Computing the volume is difficult, Discrete ~ Computational Geometry, 2:319-326, 1987.
	4	R. Bapat, Mixed discriminants of positive semidefinite matrices, Linear Algebra and its Applications 126:107- 124, 1989.
	5	A. I. Barvinok, Computing Mixed Discriminants, Mixed Volumes, and Permanents, Discrete ~4 Computational Geometry, 18:205-237 (1997).
	6	Alexander Barvinok, Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor, Random Structures & Algorithms, v.14 n.1, p.29-61, Jan. 1999 [doi>10.1002/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X]
	7	M. E. Dyer , A. M. Frieze, On the complexity of computing the volume of a polyhedron, SIAM Journal on Computing, v.17 n.5, p.967-974, October 1988 [doi>10.1137/0217060]
	8	Martin Dyer , Peter Gritzmann , Alexander Hufnagel, On The Complexity of Computing Mixed Volumes, SIAM Journal on Computing, v.27 n.2, p.356-400, April 1998 [doi>10.1137/S0097539794278384]
	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.
	10	G.P. Egorychev, The solution of van der Waerden's problem for permanents, Advances in Math., 42:299- 305, 1981.
	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).
	12	S. Friedland, A lower bound for the permanent of a doubly stochastic matrix, Annals of Mathematics, 110:167- 176, 1979.
	13	M. GrStschel~, L. Lovasz and A. Schrijver, Geometric Algorithms and Uombinatorial Optimization, Springer- Verlag, Berlin, 1988.
	14	L. Gurvits, Proving Generalized van der Waerden Conjecture - A proof of Bapat's conjecture on mixed discriminants, preprint, 1999.
	15	M. Jerrum , Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing, v.18 n.6, p.1149-1178, Dec. 1989 [doi>10.1137/0218077]
	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.
	17	N. Karmarkar , R. Karp , R. Lipton , L. Lovász , M. Luby, A Monte-Carlo algorithm for estimating the permanent, SIAM Journal on Computing, v.22 n.2, p.284-293, April 1993 [doi>10.1137/0222021]
	18	Nathan Linial , Alex Samorodnitsky , Avi Wigderson, A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.644-652, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276880]
	19	Y. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming, SIAM, Philadelphia, PA, 1994.
	20	A. Panov, On mixed discriminants connected with positive semidefinite quadratic forms, Soviet Math. Dokl. 31 (1985).
	21	R. Schneider, Convex bodies: The Brunn-Minkowski Theory, Encyclopedia of Mathematics and Its Applications, vol. 44, Cambridge University Press, New York, 1993.
	22	L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science, 8(2):189-201, 1979.

CITED BY 3

	Leonid Gurvits, Classical deterministic complexity of Edmonds' Problem and quantum entanglement, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Leonid Gurvits, Classical complexity and quantum entanglement, Journal of Computer and System Sciences, v.69 n.3, p.448-484, November 2004
	Leonid Gurvits, Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA