Enumerating vertices of covering polyhedra with totally unimodular constraint matrices

Khaled Elbassioni; Kazuhisa Makino

doi:10.1137/18M1198995

Enumerating vertices of covering polyhedra with totally unimodular constraint matrices

Khaled Elbassioni, Kazuhisa Makino

Electrical Engineering

Kyoto University

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

2 Scopus citations

Abstract

We give an incremental polynomial time algorithm for enumerating the vertices of any polyhedron P = P(A,1) = {x ∈ Rn | Ax ≥ 1, x ≥ 0}, when A is a totally unimodular matrix. Our algorithm is based on decomposing the hypergraph transversal problem for unimodular hypergraphs using Seymour's decomposition of totally unimodular matrices and may be of independent interest.

Original language	British English
Pages (from-to)	843-864
Number of pages	22
Journal	SIAM Journal on Discrete Mathematics
Volume	34
Issue number	1
DOIs	https://doi.org/10.1137/18M1198995
State	Published - 2020

Keywords

Hypergraph decomposition
Hypergraph transversals
Output polynomial time algorithm
Totally unimodular matrices
Vertex enumeration
Vertices of polyhedra

Access to Document

10.1137/18M1198995

Cite this

@article{44205cf944b54770ba800b0ec3b77294,

title = "Enumerating vertices of covering polyhedra with totally unimodular constraint matrices",

abstract = "We give an incremental polynomial time algorithm for enumerating the vertices of any polyhedron P = P(A,1) = {x ∈ Rn | Ax ≥ 1, x ≥ 0}, when A is a totally unimodular matrix. Our algorithm is based on decomposing the hypergraph transversal problem for unimodular hypergraphs using Seymour's decomposition of totally unimodular matrices and may be of independent interest.",

keywords = "Hypergraph decomposition, Hypergraph transversals, Output polynomial time algorithm, Totally unimodular matrices, Vertex enumeration, Vertices of polyhedra",

author = "Khaled Elbassioni and Kazuhisa Makino",

note = "Publisher Copyright: {\textcopyright} 2020 Society for Industrial and Applied Mathematics.",

year = "2020",

doi = "10.1137/18M1198995",

language = "British English",

volume = "34",

pages = "843--864",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - Enumerating vertices of covering polyhedra with totally unimodular constraint matrices

AU - Elbassioni, Khaled

AU - Makino, Kazuhisa

PY - 2020

Y1 - 2020

N2 - We give an incremental polynomial time algorithm for enumerating the vertices of any polyhedron P = P(A,1) = {x ∈ Rn | Ax ≥ 1, x ≥ 0}, when A is a totally unimodular matrix. Our algorithm is based on decomposing the hypergraph transversal problem for unimodular hypergraphs using Seymour's decomposition of totally unimodular matrices and may be of independent interest.

AB - We give an incremental polynomial time algorithm for enumerating the vertices of any polyhedron P = P(A,1) = {x ∈ Rn | Ax ≥ 1, x ≥ 0}, when A is a totally unimodular matrix. Our algorithm is based on decomposing the hypergraph transversal problem for unimodular hypergraphs using Seymour's decomposition of totally unimodular matrices and may be of independent interest.

KW - Hypergraph decomposition

KW - Hypergraph transversals

KW - Output polynomial time algorithm

KW - Totally unimodular matrices

KW - Vertex enumeration

KW - Vertices of polyhedra

UR - http://www.scopus.com/inward/record.url?scp=85091399425&partnerID=8YFLogxK

U2 - 10.1137/18M1198995

DO - 10.1137/18M1198995

M3 - Article

AN - SCOPUS:85091399425

SN - 0895-4801

VL - 34

SP - 843

EP - 864

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -

Enumerating vertices of covering polyhedra with totally unimodular constraint matrices

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this