A MILDLY EXPONENTIAL APPROXIMATION ALGORITHM FOR THE PERMANENT

Authors
JERRUM M VAZIRANI U
Citation
M. Jerrum et U. Vazirani, A MILDLY EXPONENTIAL APPROXIMATION ALGORITHM FOR THE PERMANENT, Algorithmica, 16(4-5), 1996, pp. 392-401
Citations number
14
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
16
Issue
4-5
Year of publication
1996
Pages
392 - 401
Database
ISI
SICI code
0178-4617(1996)16:4-5<392:AMEAAF>2.0.ZU;2-M
Abstract
A new approximation algorithm for the permanent of an rt x n 0,1-matri x is presented. The algorithm is shown to have worst-ease time complex ity exp(O(n(1/2) log(2)n)). Asymptotically, this represents a consider able improvement over the best existing algorithm which has worst-case time complexity exp(Theta(n)).