A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix

DOI10.1016/j.jcss.2010.05.002zbMath1208.68237arXivmath/0702039OpenAlexW1972778238MaRDI QIDQ1959434

Yanyan Li

Publication date: 7 October 2010

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0702039

zbMATH Keywords

perfect matchingefficient algorithms\#P hardness

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Approximation algorithms (68W25) Boolean and Hadamard matrices (15B34)

Related Items

Computing the permanent of (some) complex matrices ⋮ Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs ⋮ Correlation decay and deterministic FPTAS for counting colorings of a graph ⋮ Approximating permanents and hafnians ⋮ Matchings in Benjamini–Schramm convergent graph sequences

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Counting 1-factors in regular bipartite graphs
• A mildly exponential approximation algorithm for the permanent
• Counting independent sets up to the tree threshold
• Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Approximating the Permanent
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Matchings and walks in graphs
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents