21¢‹ICOEuî•ñ‰ÈŠw‹Zpí—ªƒRƒAv


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)


ŽÀs‘gDƒvƒƒWƒFƒNƒgŠT—vƒvƒƒWƒFƒNƒgÚ׎óÜ‚ÌЉî‰ï‹cEŠÖ˜AsŽ–What's New—š—ð‚¨–â‚¢‡‚¹
iCj Copyright 2006 Information Science and Technology Strategic Core All Rights Reserved.