DIMACS TR: 2001-12
Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
Authors: Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Leonid Khachiyan and Kazuhisa Makino
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.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-12.ps.gz
DIMACS Home Page