A generalization of permanent inequalities and applications in counting and optimization

DOI10.1016/J.AIM.2021.107657MaRDI QIDQ2020379zbMATH OpenOpenAlexFDO

Authors Nima Anari, Shayan Oveis Gharan

Publication date 23 April 2021

Published in Advances in Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.aim.2021.107657

zbMATH Keywords

determinantal point processesperfect matchingpermanentreal stable polynomialsvan der Waerden's conjecture

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Real polynomials: location of zeros (26C10) Approximation algorithms (68W25) Convex programming (90C25)

Recommendations

• A generalization of permanent inequalities and applications in counting and optimization
• Generalization of a Hadamard type inequality for permanents
• A note on the analogue of Oppenheim's inequality for permanents
• An inequality of Hadamard type for permanents
• Inequalities for the \(q\)-permanent
• A generalization of the (CN) inequality and its applications
• Inequalities for permanents involving Perron complements
• Grothendieck-type inequalities in combinatorial optimization
• On determinantal and permanental inequalities
• Chebyshev type inequalities involving permanents and their applications

Cites work

• Counting 1-factors in regular bipartite graphs
• Counting matchings in irregular bipartite graphs and random lifts
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• Determinantal point processes for machine learning
• scientific article; zbMATH DE number 5764845 (Why is no real title available?)
• Hyperbolic Polynomials and Interior Point Methods for Convex Programming
• Hyperbolic polynomials approach to van der Waerden/Schrijver-Valiant like conjectures, sharper bounds, simpler proofs and algorithmic applications
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• Maximizing determinants under partition constraints
• Multivariate Pólya-Schur classification problems in the Weyl algebra
• Nash social welfare, matrix permanent, and stable polynomials
• Negative dependence and the geometry of polynomials
• On general minimax theorems
• Polynomials with the half-plane property and matroid theory
• The membership problem in jump systems

Cited in

(10)

• Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all
• A short survey on stable polynomials, orientations and matchings
• Lower bounds for contingency tables via Lorentzian polynomials
• Hyperbolic polynomials approach to van der Waerden/Schrijver-Valiant like conjectures, sharper bounds, simpler proofs and algorithmic applications
• Real stable polynomials and matroids: optimization and counting
• A generalization of permanent inequalities and applications in counting and optimization
• Approximating real-rooted and stable polynomials, with combinatorial applications
• A real counterexample to two inequalities involving permanents
• Counting matchings via capacity-preserving operators
• Minimizing the determinant of the graph Laplacian

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2020379)