Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions

Leonid Khachiyan, Endre Boros, Khaled Elbassioni, Vladimir Gurvich

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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 {mapping} 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.

Original languageEnglish (US)
Pages (from-to)2020-2034
Number of pages15
JournalDiscrete Applied Mathematics
Volume156
Issue number11
DOIs
StatePublished - Jun 6 2008

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Dualization
  • Generation algorithms
  • Hypergraph transversals
  • Linear inequalities
  • Monotone systems of inequalities
  • Polymatroid inequalities
  • Transversal inequalities

Fingerprint

Dive into the research topics of 'Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions'. Together they form a unique fingerprint.

Cite this