A generalization of permanent inequalities and applications in counting and optimization

DOI10.1145/3055399.3055469zbMath1370.26031arXiv1702.02937OpenAlexW2593579637MaRDI QIDQ4977987

Shayan Oveis Gharan, Nima Anari

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1702.02937

zbMATH Keywords

permanentsaddle point problemdeterminantal point processstable polynomialvolume maximization

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Several-variable operator theory (spectral, Fredholm, etc.) (47A13) Inequalities for trigonometric functions and polynomials (26D05)

Related Items (21)

Counting matchings via capacity-preserving operators ⋮ Paving property for real stable polynomials and strongly Rayleigh processes ⋮ Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes ⋮ Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design ⋮ Mixed determinants and the Kadison-Singer problem ⋮ Chain-constrained spanning trees ⋮ Unnamed Item ⋮ Graph Clustering using Effective Resistance ⋮ The Ising partition function: zeros and deterministic approximation ⋮ Unnamed Item ⋮ Fisher zeros and correlation decay in the Ising model ⋮ Constant factor approximation for ATSP with two edge weights ⋮ Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration ⋮ Approximation Algorithms for D-optimal Design ⋮ Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids ⋮ Fisher Zeros and Correlation Decay in the Ising Model ⋮ Conic stability of polynomials ⋮ Gauges, loops, and polynomials for partition functions of graphical models ⋮ Unnamed Item ⋮ A Tight Analysis of Bethe Approximation for Permanent ⋮ A short survey on stable polynomials, orientations and matchings

This page was built for publication: A generalization of permanent inequalities and applications in counting and optimization