Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2014) | last year (2013) | two years ago (2012) | Notes URL

Action:

login to update

Options:








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

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
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 Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
icalp01.pdf