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
Pages (from-to)	975-990
Number of pages	16
Journal	Discrete & computational geometry
Volume	70
Issue number	3
Early online date	5 Jul 2022
DOIs	https://doi.org/10.1007/s00454-022-00406-8
Publication status	Published - 1 Oct 2023

Keywords / Materials (for Non-textual outputs)

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, 368 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. (Principal Investigator)
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 = "2023",

month = oct,

day = "1",

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

language = "English",

volume = "70",

pages = "975--990",

journal = "Discrete & computational geometry",

issn = "0179-5376",

publisher = "Springer",

number = "3",

}

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 - 2023/10/1

Y1 - 2023/10/1

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

SN - 0179-5376

VL - 70

SP - 975

EP - 990

JO - Discrete & computational geometry

JF - Discrete & computational geometry

IS - 3

ER -

Counting vertices of integral polytopes defined by facets

Abstract

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Projects

New Approaches to Counting and Sampling

Cite this