# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

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

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-31AB-E

##### 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.