The negative cycles polyhedron and hardness of checking some polyhedral properties

DOI10.1007/S10479-010-0690-5MaRDI QIDQ646701zbMATH OpenOpenAlexWikidataFDO

Authors Endre Boros, Hans Raj Tiwary, Khaled Elbassioni, Vladimir 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

0/1-polyhedrondirected graphenumeration problemextreme directionflow polytopehalf-integral polyhedrahardness of approximationmaximum supportnegative cyclesvertex

Mathematics Subject Classification ID

Boolean programming (90C09) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Generating all vertices of a polyhedron is hard
• On affine reducibility of combinatorial polytopes
• Generating all vertices of a polyhedron is hard
• The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
• Publication:4864467

Cites work

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

Cited in

(9)

• Generating all vertices of a polyhedron is hard
• Enumerating minimal transversals of hypergraphs without small holes
• Algorithms for inverse optimization problems
• Enumerating vertices of 0/1-polyhedra associated with 0/1-totally unimodular matrices
• Enumerating vertices of covering polyhedra with totally unimodular constraint matrices
• Forbidden vertices
• Generating all vertices of a polyhedron is hard
• Traversing combinatorial 0/1-polytopes via optimization
• Efficient geometric operations on convex polyhedra, with an application to reachability analysis of hybrid systems

This page was built for publication: The negative cycles polyhedron and hardness of checking some polyhedral properties

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