非表示:
キーワード:
-
要旨:
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.
