A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
From MaRDI portal
Publication:5176030
DOI10.1145/380752.380877zbMath1323.68571OpenAlexW1982027240WikidataQ56806477 ScholiaQ56806477MaRDI QIDQ5176030
Eric Vigoda, Alistair Sinclair, Mark R. Jerrum
Publication date: 27 February 2015
Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/380752.380877
Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
Concentration of permanent estimators for certain large matrices., Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree, Random path method with pivoting for computing permanents of matrices, On the Number of α-Orientations, Solution Counting Algorithms for Constraint-Centered Search Heuristics, A polynomial quantum algorithm for approximating the Jones polynomial, An upper bound for permanents of nonnegative matrices, Exact algorithms for exact satisfiability and number of perfect matchings, Optimal computation with non-unitary quantum walks, Random generation of \(2 \times 2 \times\dots \times 2 \times J\) contingency tables, Matrix permanent inequalities for approximating joint assignment matrices in tracking systems, Computing the optimal partition of variables in multi-homogeneous homotopy methods, Solution counting algorithms for constraint-centered search heuristics, Glauber dynamics on trees and hyperbolic graphs, A permanent formula for the Jones polynomial, Clifford algebras and approximating the permanent, Randomly coloring graphs with lower bounds on girth and maximum degree, Computing sparse permanents faster, Discrete quantum walks hit exponentially faster, The effect of quantum noise on algorithmic perfect quantum state transfer on NISQ processors
Cites Work
