Counting Vertices of Integral Polytopes Defined by Facets
Open Access
- 5 July 2022
- journal article
- research article
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 70 (3) , 975-990
Abstract
We present a number of complexity results concerning the problem of counting vertices of an integral polytope defined by a system of linear inequalities. The focus is on polytopes with small integer vertices, particularly 0/1 polytopes and half-integral polytopes.Keywords
All Related Versions
Funding Information
- H2020 European Research Council (947778)
- Engineering and Physical Sciences Research Council (EP/S016694/1)
This publication has 21 references indexed in Scilit:
- The complexity of approximately counting stable matchingsTheoretical Computer Science, 2012
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entriesJournal of the ACM, 2004
- The Relative Complexity of Approximate Counting ProblemsAlgorithmica, 2003
- Estimating the number of vertices of a polyhedronInformation Processing Letters, 2000
- Linear programming brings marital blissOperations Research Letters, 1989
- Random generation of combinatorial structures from a uniform distributionTheoretical Computer Science, 1986
- NP is as easy as detecting unique solutionsTheoretical Computer Science, 1986
- Decomposition of regular matroidsJournal of Combinatorial Theory, Series B, 1980
- The complexity of computing the permanentTheoretical Computer Science, 1979
- An NP-hard problem in bipartite graphsACM SIGACT News, 1975