Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop
Show entries of:
this year
(2016) |
last year
(2015) |
two years ago
(2014) |
Notes URL
Action:
login to update
Options:
Goto entry point
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
Attachment(s)
:
icalp01.pdf (184.36 KB)
Booktitle*:
Automata, Languages and Programming, 28th International Colloquium, ICALP 2001
Event, URLs
URL of the conference:
URL for downloading the paper:
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
Edit History (please click the blue arrow to see the details)
Attachment Section
View attachments here:
icalp01.pdf
icalp01.pdf