MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Khachiyan, Leonid
Boros, Endre
Borys, Konrad
Elbassioni, Khaled M.
Gurvich, Vladimir		dblp
dblp
dblp
dblp
dblp
Not MPG Author(s):
Khachiyan, Leonid
Boros, Endre
Borys, Konrad
Gurvich, Vladimir
Editor(s):
BibTeX cite key*:
Elbassioni2006a
Title, Booktitle
Title*:
Generating All Vertices of a Polyhedron is Hard
Booktitle*:
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'06
Event, URLs
Conference URL::
Downloading URL:
http://delivery.acm.org/10.1145/1110000/1109640/p758-khachiyan.pdf?key1=1109640&key2=7758580711&coll=GUIDE&dl=GUIDE&CFID=13785645&CFTOKEN=14577517
Event Address*:
Miami, FL, USA
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
22 January 2006
Event End Date:
24 January 2006
Publisher
Name*:
ACM / SIAM
URL:
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
January
Pages:
758-765
Year*:
2006
VG Wort Pages:
ISBN/ISSN:
0-89871-605-5
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We show that generating all negative cycles of a weighted graph is a hard enumeration problem, in both the directed and undirected cases. More precisely, given a family of negative (directed) cycles, it is an NP-complete problem to decide whether this family can be extended or there are no other negative (directed) cycles in the graph, implying that (directed) negative cycles cannot be generated in polynomial output time, unless P=NP. As a corollary, we solve in the negative two well-known generating problems from linear programming: (i) Given an infeasible system of linear inequalities, generating all minimal infeasible subsystems is hard. Yet, for generating 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 the case of bounded polyhedra the complexity remains open
URL for the Abstract:
http://doi.acm.org/10.1145/1109557.1109640
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Elbassioni2006a,
AUTHOR = {Khachiyan, Leonid and Boros, Endre and Borys, Konrad and Elbassioni, Khaled M. and Gurvich, Vladimir},
 TITLE = {Generating All Vertices of a Polyhedron is Hard},
 BOOKTITLE = {Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'06},
 PUBLISHER = {ACM / SIAM},
 YEAR = {2006},
 PAGES = {758--765},
 ADDRESS = {Miami, FL, USA},
 MONTH = {January},
 ISBN = {0-89871-605-5},
}

Entry last modified by Christine Kiesel, 05/02/2007
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Khaled Elbassioni		Created
04/05/2006 02:33:05 AM
Revisions
10.
9.
8.
7.
6.		Editor(s)
Christine Kiesel
Christine Kiesel
Regina Kraemer
Christine Kiesel
Christine Kiesel		Edit Dates
02.05.2007 15:30:08
30.04.2007 18:26:36
04/16/2007 10:02:09 AM
07.02.2007 19:01:04
07.02.2007 18:57:20