MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Boros, Endre
Elbassioni, Khaled M.
Khachiyan, Leonid
Gurvich, Vladimir
Makino, Kazuhisa		dblp
dblp
dblp
dblp
dblp
Not MPG Author(s):
Boros, Endre
Gurvich, Vladimir
Khachiyan, Leonid
Makino, Kazuhisa
Editor(s):
Not MPII Editor(s):
Fernando Orejas,
Paul G. Spirakis,
Jan van Leeuwen
BibTeX cite key*:
Elbassioni2001
Title, Booktitle
Title*:
On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities
icalp01.pdf (184.36 KB)
Booktitle*:
Automata, Languages and Programming, 28th International Colloquium, ICALP 2001
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Heraklion, Crete, Greece
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
8 July 2001
Event End Date:
12 July 2001
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
2076
Number:
Month:
July
Pages:
92-103
Year*:
2001
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We consider the problem of enumerating all minimal integer solutions of a monotone system of linear inequalities. We first show that for any monotone system of linear inequalities in variables, the number of maximal infeasible integer vectors is at most times the number of minimal integer solutions to the system. This bound is accurate up to a factor and leads to a polynomial-time reduction of the enumeration problem to a natural generalization of the well-known dualization problem for hypergraphs, in which dual pairs of hypergraphs are replaced by dual collections of integer vectors in a box. We provide a quasi-polynomial algorithm for the latter dualization problem. These results imply, in particular, that the problem of incrementally generating minimal integer solutions of a monotone system of linear inequalities can be done in quasi-polynomial time.
Keywords:
Integer programming, complexity of incremental algorithms, dualization, quasi-polynomial time, monotone discrete binary functions, monotone inequalities, regular discrete functions.
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{Elbassioni2001,
AUTHOR = {Boros, Endre and Elbassioni, Khaled M. and Khachiyan, Leonid and Gurvich, Vladimir and Makino, Kazuhisa},
 TITLE = {On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities},
 BOOKTITLE = {Automata, Languages and Programming, 28th International Colloquium, ICALP 2001},
 PUBLISHER = {Springer},
 YEAR = {2001},
 VOLUME = {2076},
 PAGES = {92--103},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Heraklion, Crete, Greece},
 MONTH = {July},
}

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
02/22/2005 19:25:04
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Khaled Elbassioni
Khaled Elbassioni
Edit Dates
02.05.2007 16:47:56
02.06.2006 15:17:45
04/20/2006 06:45:07 PM
02/22/2005 07:25:04 PM

File Attachment Icon
icalp01.pdf