On generating all minimal integer solutions for a monotone system of linear inequalities

E. Boros, K. Elbassioni, V. Gurvich, L. Khachiyan, K. Makino

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

10 Scopus citations

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 r linear inequalities in n variables, the number of maximal infeasible integer vectors is at most rn times the number of minimal integer solutions to the system. This bound is accurate up to a polylog(r) 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.

Original languageBritish English
Title of host publicationAutomata, Languages and Programming - 28th International Colloquium, ICALP 2001, Proceedings
EditorsFernando Orejas, Paul G. Spirakis, Jan van Leeuwen
PublisherSpringer Verlag
Pages92-103
Number of pages12
ISBN (Print)3540422870, 9783540422877
DOIs
StatePublished - 2001
Event28th International Colloquium on Automata, Languages and Programming, ICALP 2001 - Crete, Greece
Duration: 8 Jul 200112 Jul 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2076 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference28th International Colloquium on Automata, Languages and Programming, ICALP 2001
Country/TerritoryGreece
CityCrete
Period8/07/0112/07/01

Keywords

  • Cmplexity of incremental algorithms
  • Dalization
  • Integer programming
  • Mnotone discrete binary functions
  • Mnotone inequalities
  • Qasi-polynomial time
  • Rgular discrete functions

Fingerprint

Dive into the research topics of 'On generating all minimal integer solutions for a monotone system of linear inequalities'. Together they form a unique fingerprint.

Cite this