## Abstract

We consider monotone ∨, ∧-formulae φ of m atoms, each of which is a monotone inequality of the form f_{i}(x) ≥ t_{i} over the integers, where for i = 1,..., m, f_{i}: ℤ^{n} → ℝ is a given monotone function and t_{i} 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 language | British English |
---|---|

Pages (from-to) | 556-567 |

Number of pages | 12 |

Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Volume | 3618 |

DOIs | |

State | Published - 2005 |

Event | 30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005 - Gdansk, Poland Duration: 29 Aug 2005 → 2 Sep 2005 |