Enumerating vertices of 0/1-polyhedra associated with 0/1-totally unimodular matrices

DOI10.4230/LIPICS.SWAT.2018.18MaRDI QIDQ5116482zbMATH OpenOpenAlexFDO

Authors Kazuhisa Makino, Khaled Elbassioni

Publication date 25 August 2020

Full work available at URL https://arxiv.org/abs/1707.03914

zbMATH Keywords

vertex enumerationtotally unimodular matriceshypergraph transversalshypergraph decompositionvertices of polyhedraoutput polynomial-time algorithm

Mathematics Subject Classification ID

Factorization of matrices (15A23) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Matrices of integers (15B36) Hypergraphs (05C65)

Abstract: We give an incremental polynomial time algorithm for enumerating the vertices of any polyhedron $$, 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.

Recommendations

• Enumerating vertices of covering polyhedra with totally unimodular constraint matrices
• The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
• Enumerating integer points in polytopes with bounded subdeterminants
• A POLYNOMIAL ALGORITHM FOR ENUMERATING ALL VERTICES OF A BASE POLYHEDRON
• On a Class of Totally Unimodular Matrices

Cites work

• scientific article; zbMATH DE number 2186837 (Why is no real title available?)
• scientific article; zbMATH DE number 3854804 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 53949 (Why is no real title available?)
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• An algorithm for determining all extreme points of a convex polytope
• Combinatorial optimization. Packing and covering
• Complexity of identification and dualization of positive Boolean functions
• Decomposition of regular matroids
• Enumeration of Nash equilibria for two-player games
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Generating all vertices of a polyhedron is hard
• How good are convex hull algorithms?
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the Complexity of Some Enumeration Problems for Matroids
• On the width—length inequality
• Primal-dual methods for vertex and facet enumeration
• Reverse search for enumeration
• The Complexity of Vertex Enumeration Methods
• The negative cycles polyhedron and hardness of checking some polyhedral properties
• The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable

Cited in

(11)

• Birkhoff's polytope and unistochastic matrices, \(N=3\) and \(N=4\)
• Integral boundary points of convex polyhedra
• Enumerating minimal transversals of hypergraphs without small holes
• Traversing combinatorial 0/1-polytopes via optimization
• On the combinatorial structure of \(0/1\)-matrices representing nonobtuse simplices
• Enumerating integer points in polytopes with bounded subdeterminants
• Isolating a vertex via lattices: polytopes with totally unimodular faces
• Isolating a vertex via lattices: polytopes with totally unimodular faces
• Enumerating vertices of covering polyhedra with totally unimodular constraint matrices
• On \(0,\pm 1\) matrices, odd vectors, and bisubmodular polyhedra
• scientific article; zbMATH DE number 1972778 (Why is no real title available?)

This page was built for publication: Enumerating vertices of \(0/1\)-polyhedra associated with \(0/1\)-totally unimodular matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116482)