A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary

DOI10.1007/s00454-001-0083-2zbMath1008.68145OpenAlexW1535255862MaRDI QIDQ1611062

Leonid Gurvits, Alex Samorodnitsky

Publication date: 20 August 2002

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-001-0083-2

zbMATH Keywords

polynomial-time algorithmRado's theorem

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

The Van der Waerden conjecture for mixed discriminants, Classical complexity and quantum entanglement, On the Computability of Continuous Maximum Entropy Distributions with Applications, On the Complexity of Constrained Determinantal Point Processes, Inapproximability of positive semidefinite permanents and quantum state tomography, Concentration of the mixed discriminant of well-conditioned matrices, Relative entropy optimization and its applications, Enumerating Contingency Tables via Random Permanents, Stability and complexity of mixed discriminants, A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor, Operator scaling: theory and applications, Scaling matrices and counting the perfect matchings in graphs, Conic Geometric Optimization on the Manifold of Positive Definite Matrices, Bézout-Type Inequality in Convex Geometry, Heat flow and a faster algorithm to compute the surface area of a convex body