Generating all vertices of a polyhedron is hard.
“úŽžF•½¬18”N8ŒŽ4“ú(‹à)@15:00`17:00
êŠF“Œ‹ž‘åŠw@HŠw•”‚U†ŠÙ‚RŠKƒZƒ~ƒi[ŽºA/D
u‰‰ŽÒFDr.@Vladimir A.Gurvich
@@@@@
(Rutgers Center for Operations Reseach,
@@@@@
The State University of New Jersey,
@@@@@
Adjunct Professor and@Researcher )
ƒ^ƒCƒgƒ‹FGenerating all vertices of a polyhedron is hard.
ŠT—v
We show that generating all negative directed cycles of a directed graph is a hard generating problem. More precisely, given a digraph and a collection of its negative dicycles, it is NP-hard to decide whether this collection is complete.
As a corollary we solve in negative two well-known generating problems from linear programming:
(i) Given an infeasible system of linear inequalities, generating all its minimal infeasible subsystems(so-called Helly subsystems) is hard.
@
Yet, for maximal feasible subsystems the complexity remains open.
(ii) Given a feasible system of linear inequalities, generating all vertices of the corresponding polyhedron@is hard. Yet, in case of bounded polyhedra the complexity remains open
(˜A—æF”—î•ñŠw@–q–ì@˜a‹v@“àü‚Q‚U‚W‚X‚U) |