@inproceedings{dcaaf65f5c6e40d89c3c75899ac8a876,

title = "On generating all minimal integer solutions for a monotone system of linear inequalities",

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.",

keywords = "Cmplexity of incremental algorithms, Dalization, Integer programming, Mnotone discrete binary functions, Mnotone inequalities, Qasi-polynomial time, Rgular discrete functions",

author = "E. Boros and K. Elbassioni and V. Gurvich and L. Khachiyan and K. Makino",

year = "2001",

doi = "10.1007/3-540-48224-5_8",

language = "British English",

isbn = "3540422870",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "92--103",

editor = "Fernando Orejas and Spirakis, {Paul G.} and {van Leeuwen}, Jan",

booktitle = "Automata, Languages and Programming - 28th International Colloquium, ICALP 2001, Proceedings",

address = "Germany",

note = "28th International Colloquium on Automata, Languages and Programming, ICALP 2001 ; Conference date: 08-07-2001 Through 12-07-2001",

}