# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Dual-Bounded Generating Problems: 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. (2002).
Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities.*
SIAM Journal on Computing,* *31*, 20.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0019-ED69-1

##### 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 all minimal integer solutions to a monotone system of
linear inequalities can be done in quasi-polynomial time.