@inproceedings{f598b5fd9f9b464aaae3ed91b237060a,
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 = "https://doi.org/10.1007/3-540-48224-5_8",
language = "American 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",
}