A mildly exponential approximation algorithm for the permanent

DOI10.1007/BF01940871zbMath0857.68053OpenAlexW2029212237MaRDI QIDQ1923855

Umesh V. Vazirani, Mark R. Jerrum

Publication date: 18 February 1997

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01940871

zbMATH Keywords

approximation algorithmperfect matchings

Mathematics Subject Classification ID

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

Related Items

A permanent formula with many zero-valued terms, An exponential time 2-approximation algorithm for bandwidth, Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor, A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix, Calculation of the permanent of a sparse positive matrix, Clifford algebras and approximating the permanent

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• Random generation of combinatorial structures from a uniform distribution
• An analysis of Monte Carlo algorithm for estimating the permanent
• Approximating the Permanent
• A Monte-Carlo Algorithm for Estimating the Permanent