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

DOI10.4230/LIPICS.SWAT.2018.18zbMATH Open1477.68467arXiv1707.03914OpenAlexW2964248860MaRDI QIDQ5116482FDOQ5116482

Kazuhisa Makino, Khaled Elbassioni

Publication date: 25 August 2020

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.

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

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

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)

Cites Work

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

Cited In (5)

• Birkhoff's polytope and unistochastic matrices, \(N=3\) and \(N=4\)
• Enumerating Minimal Transversals of Hypergraphs without Small Holes
• On the combinatorial structure of \(0/1\)-matrices representing nonobtuse simplices
• Title not available (Why is that?)
• On \(0,\pm 1\) matrices, odd vectors, and bisubmodular polyhedra

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)