Title | ||
---|---|---|
A Generalization of Permanent Inequalities and Applications in Counting and Optimization. |
Abstract | ||
---|---|---|
A polynomial pââ[z1,â¦,zn] is real stable if it has no roots in the upper-half complex plane. Gurvitsâs permanent inequality gives a lower bound on the coefficient of the z1z2⦠zn monomial of a real stable polynomial p with nonnegative coefficients. This fundamental inequality has been used to attack several counting and optimization problems. Here, we study a more general question: Given a stable multilinear polynomial p with nonnegative coefficients and a set of monomials S, we show that if the polynomial obtained by summing up all monomials in S is real stable, then we can lower bound the sum of coefficients of monomials of p that are in S. We also prove generalizations of this theorem to (real stable) polynomials that are not multilinear. We use our theorem to give a new proof of Schrijverâs inequality on the number of perfect matchings of a regular bipartite graph, generalize a recent result of Nikolov and Singh, and give deterministic polynomial time approximation algorithms for several counting problems. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1145/3055399.3055469 | STOC |
Keywords | DocType | Volume |
Stable Polynomial,Saddle Point Problem,Permanent,Determinantal Point Process,Volume Maximization | Conference | abs/1702.02937 |
ISSN | Citations | PageRank |
0737-8017 | 8 | 0.58 |
References | Authors | |
11 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nima Anari | 1 | 79 | 14.83 |
Shayan Oveis Gharan | 2 | 323 | 26.63 |