DocumentCode
180735
Title
Bounds on the Permanent and Some Applications
Author
Gurvits, Leonid ; Samorodnitsky, Alex
Author_Institution
Dept. of Comput. Sci., City Coll. of New York, New York, NY, USA
fYear
2014
fDate
18-21 Oct. 2014
Firstpage
90
Lastpage
99
Abstract
We give new lower and upper bounds on the permanent of a doubly stochastic matrix. Combined with previous work, this improves on the deterministic approximation factor. We also give a combinatorial application of the lower bound, proving S. Friedland\´s "Asymptotic Lower Matching Conjecture"for the monomer-dimer problem.
Keywords
approximation theory; combinatorial mathematics; matrix algebra; stochastic processes; asymptotic lower-matching conjecture; combinatorial application; deterministic approximation factor improvement; doubly-stochastic matrix permanent; lower bounds; monomer-dimer problem; upper bounds; Approximation algorithms; Approximation methods; Bipartite graph; Computer science; Educational institutions; Polynomials; Upper bound; approximation of the permanent; bounds on the permanent;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on
Conference_Location
Philadelphia, PA
ISSN
0272-5428
Type
conf
DOI
10.1109/FOCS.2014.18
Filename
6978993
Link To Document