de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44374

Elbassioni,  Khaled M.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Boros, E., Elbassioni, K. M., Khachiyan, L., Gurvich, V., & Makino, K. (2001). On Generating All Minimal Integer Solutions for a Monotone System of Linear Inequalities. In Automata, Languages and Programming, 28th International Colloquium, ICALP 2001 (pp. 92-103). Berlin, Germany: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-31AB-E
Zusammenfassung
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.