Counting vertices of integral polytopes defined by facets

Heng Guo, Mark Jerrum*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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.
Original languageEnglish
Pages (from-to)975-990
Number of pages16
JournalDiscrete & computational geometry
Volume70
Issue number3
Early online date5 Jul 2022
DOIs
Publication statusPublished - 1 Oct 2023

Keywords / Materials (for Non-textual outputs)

  • 0/1 polytopes
  • approximation algorithms
  • computational complexity of counting
  • totally unimodular matrices

Fingerprint

Dive into the research topics of 'Counting vertices of integral polytopes defined by facets'. Together they form a unique fingerprint.

Cite this