Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions |
| |
Authors: | Leonid Khachiyan Khaled Elbassioni Vladimir Gurvich |
| |
Institution: | a RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ 08854-8003, USA b Max-Planck-Institut für Informatik, 66123 Saarbrücken, Germany |
| |
Abstract: | We consider monotone ∨,∧-formulae φ of m atoms, each of which is a monotone inequality of the form fi(x)?ti over the integers, where for i=1,…,m, fi:Zn?R is a given monotone function and ti is a given threshold. We show that if the ∨-degree of φ is bounded by a constant, then for linear, transversal and polymatroid monotone inequalities all minimal integer vectors satisfying φ 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 disjunctive programming, data mining, matroid and reliability theory. |
| |
Keywords: | Dualization Hypergraph transversals Generation algorithms Monotone systems of inequalities Linear inequalities Transversal inequalities Polymatroid inequalities |
本文献已被 ScienceDirect 等数据库收录! |
|