Counting vertices of integral polytopes defined by facets

DOI10.1007/s00454-022-00406-8arXiv2105.01469WikidataQ114229297 ScholiaQ114229297MaRDI QIDQ6050234

Heng Guo, Mark R. Jerrum

Publication date: 12 October 2023

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmstotally unimodular matrices0/1 polytopescomputational complexity of counting

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• The complexity of approximately counting stable matchings
• The complexity of computing the permanent
• The complexity of approximating conservative counting CSPs
• The complexity of recognizing linear systems with certain integrality properties
• Random generation of combinatorial structures from a uniform distribution
• NP is as easy as detecting unique solutions
• A decomposition theory for matroids. V: Testing of matrix total unimodularity
• Linear programming brings marital bliss
• Decomposition of regular matroids
• Estimating the number of vertices of a polyhedron
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The relative complexity of approximate counting problems
• On recognizing integer polyhedra
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Total Dual Integrality of Rothblum's Description of the Stable-Marriage Polyhedron
• On Approximation Algorithms for # P
• Canonical Paths for MCMC: from Art to Science
• Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid
• Integer Programming: Methods, Uses, Computations