Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:


URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section