2005-12: Generating All Minimal Integral Solutions to AND-OR Systems of Monotone Inequalities: Conjunctions are Easier than Disjunctions

DIMACS TR: 2005-12

Generating All Minimal Integral Solutions to AND-OR Systems of Monotone Inequalities: Conjunctions are Easier than Disjunctions

Authors: Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Leonid Khachiyan

ABSTRACT
We consider monotone $\vee, \wedge$-formulae $\phi$ of $m$ atoms, each of which is a monotone inequality of the form $f_i(x)\geq t_i$ over the integers, where for $i=1,\ldots,m$, $f_i:\ZZ^n\mapsto\ RR$ is a given monotone function and $t_i$ is a given threshold. We show that if the $\vee$-degree of $\phi$ is bounded by a c onstant, then for linear, transversal and polymatroid monotone inequalities all minimal integer vectors satisfying $\phi$ can be generated in incremental quasi-polynomial time. In contrast, the enumeration problem for the disjunction of $m$ inequalities is NP-hard when $m$ is part of the input. We also discuss some applications of the above results in di sjunctive programming, data mining, matroid and reliability theory.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-12.ps.gz

DIMACS Home Page