A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

DOI10.1145/380752.380877zbMath1323.68571DBLPconf/stoc/JerrumSV01OpenAlexW1982027240WikidataQ56806477 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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (20)

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

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries