The negative cycles polyhedron and hardness of checking some polyhedral properties

DOI10.1007/s10479-010-0690-5zbMath1225.90143WikidataQ59560546 ScholiaQ59560546MaRDI QIDQ646701

Endre Boros, Hans Raj Tiwary, Khaled M. Elbassioni, Vladimir A. Gurvich

Publication date: 17 November 2011

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-010-0690-5

zbMATH Keywords

enumeration problem; extreme direction; directed graph; vertex; hardness of approximation; negative cycles; 0/1-polyhedron; flow polytope; half-integral polyhedra; maximum support

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C60: Abstract computational complexity for mathematical programming problems

90C09: Boolean programming

Related Items

Unnamed Item, Enumerating Minimal Transversals of Hypergraphs without Small Holes, Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices, Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices, Forbidden Vertices, Efficient geometric operations on convex polyhedra, with an application to reachability analysis of hybrid systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of recognizing linear systems with certain integrality properties
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
• Primal-dual methods for vertex and facet enumeration
• Efficient enumeration of the vertices of polyhedra associated with network LP's
• How good are convex hull algorithms?
• A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts
• Reverse search for enumeration
• On recognizing integer polyhedra
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Automata, Languages and Programming
• Generating all vertices of a polyhedron is hard