Generating all vertices of a polyhedron is hard (Q5920505): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q59560590, #quickstatements; #temporary_batch_1707232231678 |
Removed claim: author (P16): Item:Q1315410 |
||
Property / author | |||
Property / author: Leonid G. Khachiyan / rank | |||
Revision as of 16:04, 27 February 2024
scientific article; zbMATH DE number 5264627
Language | Label | Description | Also known as |
---|---|---|---|
English | Generating all vertices of a polyhedron is hard |
scientific article; zbMATH DE number 5264627 |
Statements
Generating all vertices of a polyhedron is hard (English)
0 references
16 April 2008
0 references
Consider a directed edge-weighted graph \(G\) where the arcs are weighted by real values. A cycle is negative if the sum of its edge weights is negative. The number of negative cycles may be exponential in the size of the input, i.e. the size of \(G\) and the weights. The main result says that enumerating all negative cycles is NP-hard, even if the edge weights consist of only two different values. The same result holds for the undirected case. As a consequence, enumerating all minimal infeasible subsystems of a system of linear inequalities is NP-hard. This is even true for linear systems involving at most two variables in each inequality. For generating maximal feasible subsystems the complexity is open. Enumerating all vertices of a rational polyhedron, given as the intersection of finitely many half-spaces, is NP-hard. For bounded polyhedra the complexity remains open.
0 references
directed edge weighted graph
0 references
enumeration
0 references
negative cycles
0 references
infeasible subsystems of system of linear inequalities
0 references
NP-hard
0 references