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
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;
Conference_Titel :
Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on
Conference_Location :
Philadelphia, PA
DOI :
10.1109/FOCS.2014.18
