A mildly exponential approximation algorithm for the permanent

Similar Works

Action	Title	Year	Authors
+	A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries	2000	Mark Jerrum Eric Vigoda
+	A mildly exponential approximation algorithm for the permanent	1996	M. Jerrum U. Vazirani
+ PDF Chat	A deterministic approximation algorithm for computing the permanent of a <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mn>1</mml:mn></mml:math> matrix	2010	David Gamarnik Dmitriy Katz
+	Probabilistic and Deterministic Approximations of the Permanent	1999	Avi Wigderson
+	A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries	2001	Mark Jerrum Alistair Sinclair Eric Vigoda
+	A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries	2004	Mark Jerrum Alistair Sinclair Eric Vigoda
+	A Monte-Carlo Algorithm for Estimating the Permanent	1993	Narendra Karmarkar Richard M. Karp Richard Lipton László Lovász Michael Luby
+	A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents	2000	Nathan Linial Alex Samorodnitsky Avi Wigderson
+	An Almost Linear Time Approximation Algorithm for the Permanent of a Random (0-1) Matrix	2004	Martin Fürer Shiva Prasad Kasiviswanathan
+	An upper bound for permanents of nonnegative matrices	2006	Alex Samorodnitsky
+	An approximation algorithm for computing the permanent	1980	Leslie M. Goldschlager
+	An upper bound for the permanent of (0,1)-matrices	2003	Heng Liang Fengshan Bai
+	The Computational Complexity of Computing the Permanent of a Matrix	2003	Craig Alan Feinstein
+	A Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix	2007	David Gamarnik Dmitriy Katz
+	An Upper Bound for the Permanent of a 3-Dimensional (0, 1)-Matrix	1987	Stephen J. Dow Peter M. Gibson
+	A Permanent Algorithm with exp[Ω (n ^{1/3}/2 ln n )] Expected Speedup for 0-1 Matrices	2002	Bax Franklin
+	Polynomial algorithms for computing the permanents of some matrices	1997	A. P. ILYICHEV Grigoriy P. Kogan V. N. Shevchenko
+	FPRAS Approximation of the Matrix Permanent in Practice	2020	James C. Newman
+ PDF Chat	A Tight Analysis of Bethe Approximation for Permanent	2019	Nima Anari Alireza Rezaei
+ PDF Chat	Computing sparse permanents faster	2005	Rocco A. Servedio Andrew Wan

Works That Cite This (10)

Action	Title	Year	Authors
+	On the Complexity of Some Basic Problems in Computational Convexity	1994	Peter Gritzmann Victor Klee
+	NP-complete problems have a version that's hard to approximate	2002	David Zuckerman
+	Markov chains and polynomial time algorithms	2002	Ravi Kannan
+	An optimal algorithm for Monte Carlo estimation	2002	Paul Dagum Richard M. Karp Michael Luby Sheldon M. Ross
+ PDF Chat	Statistical problems involving permutations with restricted positions	2001	Persi Diaconis Ronald Graham Susan Holmes
+	The Markov chain Monte Carlo method: an approach to approximate counting and integration	1996	Mark Jerrum Alistair Sinclair
+	Computing the permanent by importance sampling method	1996	N. Yu. Kuznetsov
+	Exploration of NP-hard enumeration problems by simulated annealing — the spectrum values of permanents	1999	Yaghout Nourani Bjarne Andresen
+	Matching and Vertex Packing: How “hard” are They?	1993	Michael D. Plummer
+	Approximating the number of monomer-dimer coverings of a lattice	1996	Claire Kenyon Dana Randall Alistair Sinclair

Works Cited by This (8)

Action	Title	Year	Authors
+	Randomised algorithms for counting and generating combinatorial structures	1988	Alistair Sinclair
+	A Monte-Carlo Algorithm for Estimating the Permanent	1993	Narendra Karmarkar Richard M. Karp Richard Lipton László Lovász Michael Luby
+	The complexity of computing the permanent	1979	Leslie G. Valiant
+	How hard is it to marry at random? (On the approximation of the permanent)	1986	Arndt Bröder
+	Monte-Carlo algorithms for enumeration and reliability problems	1983	Richard M. Karp Michael Luby
+ PDF Chat	Approximating the Permanent	1989	Mark Jerrum Alistair Sinclair
+	An analysis of a Monte Carlo algorithm for estimating the permanent	1995	Alan Frieze Mark Jerrum
+	Random generation of combinatorial structures from a uniform distribution	1986	Mark Jerrum Leslie G. Valiant Vijay V. Vazirani