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

DOI<link itemprop=identifier href="https://doi.org/10.1002/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X" /><29::AID-RSA2>3.0.CO;2-X 10.1002/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-XzbMath0961.68059OpenAlexW2116488705MaRDI QIDQ4705350

Alexander I. Barvinok

Publication date: 19 December 1999

Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(1999010)14:1<29::aid-rsa2>3.0.co;2-x

zbMATH Keywords

randomized polynomial time algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Combinatorial optimization (90C27)

Related Items (20)

A general law of large permanent ⋮ Concentration of permanent estimators for certain large matrices. ⋮ Computing the permanent of (some) complex matrices ⋮ Classical complexity and quantum entanglement ⋮ Hafnians, perfect matchings and Gaussian matrices ⋮ Singular values of Gaussian matrices and permanent estimators ⋮ Solution Counting Algorithms for Constraint-Centered Search Heuristics ⋮ Fast algorithms of bath calculations in simulations of quantum system-bath dynamics ⋮ Convexity of the image of a quadratic map via the relative entropy distance ⋮ Approximating permanents and hafnians ⋮ A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes ⋮ Solution counting algorithms for constraint-centered search heuristics ⋮ Estimating the permanent by importance sampling from a finite population ⋮ A permanent formula for the Jones polynomial ⋮ Clifford algebras and approximating the permanent ⋮ Stability and complexity of mixed discriminants ⋮ Non-commutative circuits and the sum-of-squares problem ⋮ Matrix permanent and quantum entanglement of permutation invariant states ⋮ Immanants and finite point processes ⋮ Noncommutativity makes determinants hard

Cites Work

• Unnamed Item
• Random generation of combinatorial structures from a uniform distribution
• The solution of van der Waerden's problem for permanents
• Two combinatorial applications of the Aleksandrov-Fenchel inequalities
• Computing mixed discriminants, mixed volumes, and permanents
• An analysis of Monte Carlo algorithm for estimating the permanent
• A mildly exponential approximation algorithm for the permanent
• Approximating the Permanent
• A Monte-Carlo Algorithm for Estimating the Permanent
• Random walks in a convex body and an improved volume algorithm
• Approximating the permanent: A simple approach
• Two Algorithmic Results for the Traveling Salesman Problem
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents

This page was built for publication: Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor