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

DOI10.1145/335305.335311MaRDI QIDQ3191970zbMATH OpenOpenAlexFDO

Authors Leonid Gurvits, Alex Samorodnitsky

Publication date 26 September 2014

Published in Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/335305.335311

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
• A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor
• A random polynomial-time algorithm for approximating the volume of convex bodies
• On The Complexity of Computing Mixed Volumes
• Near-optimal deterministic algorithms for volume computation via M-ellipsoids
• Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
• Mathematical Foundations of Computer Science 2005
• Polynomial time algorithms for maximizing the intersection volume of polytopes
• Polynomial time \(\rho\)-locally maximum volume search

Cited in

(11)

• A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor
• Computing mixed discriminants, mixed volumes, and permanents
• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
• Classical complexity and quantum entanglement
• Operator scaling: theory and applications
• Spectral analysis of matrix scaling and operator scaling
• Stability and complexity of mixed discriminants
• Mathematical Foundations of Computer Science 2005
• Bézout-Type Inequality in Convex Geometry
• The Van der Waerden conjecture for mixed discriminants
• Concentration of the mixed discriminant of well-conditioned matrices

This page was built for publication: A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3191970)