Counting vertices of integral polytopes defined by facets

Heng Guo; Mark Jerrum

doi:10.1007/s00454-022-00406-8

Counting vertices of integral polytopes defined by facets

Heng Guo, Mark Jerrum^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Number of pages	16
Journal	Discrete & computational geometry
Early online date	5 Jul 2022
DOIs	https://doi.org/10.1007/s00454-022-00406-8
Publication status	E-pub ahead of print - 5 Jul 2022

Keywords

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

Access to Document

10.1007/s00454-022-00406-8Licence: Creative Commons: Attribution (CC-BY)

Counting Vertices_GUO_DOA02052022_VOR_CC-BYFinal published version, 350 KBLicence: Creative Commons: Attribution (CC-BY)

https://link.springer.com/article/10.1007/s00454-022-00406-8Licence: Creative Commons: Attribution (CC-BY)

New Approaches to Counting and Sampling
Guo, H.
EU government bodies
1/01/21 → 31/12/25
Project: Research

Cite this

@article{aafe8bbb416a40db8ec40b65306df75d,

title = "Counting vertices of integral polytopes defined by facets",

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 = "0/1 polytopes, approximation algorithms, computational complexity of counting, totally unimodular matrices",

author = "Heng Guo and Mark Jerrum",

note = "Funding Information: HG has received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (Grant Agreement No. 947778). Funding Information: MJ was supported by Grant EP/S016694/1 {\textquoteleft}Sampling in hereditary classes{\textquoteright} from the Engineering and Physical Sciences Research Council (EPSRC) of the UK. Publisher Copyright: {\textcopyright} 2022, The Author(s).",

year = "2022",

month = jul,

day = "5",

doi = "10.1007/s00454-022-00406-8",

language = "English",

journal = "Discrete & computational geometry",

issn = "0179-5376",

publisher = "Springer New York",

}

TY - JOUR

T1 - Counting vertices of integral polytopes defined by facets

AU - Guo, Heng

AU - Jerrum, Mark

N1 - Funding Information: HG has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 947778). Funding Information: MJ was supported by Grant EP/S016694/1 ‘Sampling in hereditary classes’ from the Engineering and Physical Sciences Research Council (EPSRC) of the UK. Publisher Copyright: © 2022, The Author(s).

PY - 2022/7/5

Y1 - 2022/7/5

N2 - 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.

AB - 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.

KW - 0/1 polytopes

KW - approximation algorithms

KW - computational complexity of counting

KW - totally unimodular matrices

U2 - 10.1007/s00454-022-00406-8

DO - 10.1007/s00454-022-00406-8

M3 - Article

JO - Discrete & computational geometry

JF - Discrete & computational geometry

SN - 0179-5376

ER -

Counting vertices of integral polytopes defined by facets

Abstract

Keywords

Access to Document

Fingerprint

Projects

New Approaches to Counting and Sampling

Cite this