Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities

DOI10.1137/S0097539701388768zbMath1041.68064OpenAlexW1998987607WikidataQ59560669 ScholiaQ59560669MaRDI QIDQ3149887

Kazuhisa Makino, Endre Boros, Leonid G. Khachiyan, Khaled M. Elbassioni, Vladimir A. Gurvich

Publication date: 29 September 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539701388768

zbMATH Keywords

integer programmingdualizationquasi-polynomial timecomplexity of incremental algorithmsmonotone discrete binary functionsmonotone inequalitiesregular discrete functions

Mathematics Subject Classification ID

Computational learning theory (68Q32) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Related Items

Dual-bounded generating problems: Weighted transversals of a hypergraph ⋮ A note on systems with max-min and max-product constraints ⋮ Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data ⋮ A global parallel algorithm for the hypergraph transversal problem ⋮ On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs ⋮ An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation ⋮ On Dualization over Distributive Lattices ⋮ The Minimal Hitting Set Generation Problem: Algorithms and Computation ⋮ Monomial Tropical Cones for Multicriteria Optimization ⋮ Dualization problem over the product of chains: asymptotic estimates for the number of solutions ⋮ A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs ⋮ Enumerating Minimal Transversals of Hypergraphs without Small Holes ⋮ Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions ⋮ Computational aspects of monotone dualization: a brief survey ⋮ On the complexity of monotone dualization and generating minimal hypergraph transversals ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ Tropical polar cones, hypergraph transversals, and mean payoff games ⋮ On the generation of circuits and minimal forbidden sets ⋮ Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry ⋮ Generating dual-bounded hypergraphs ⋮ On the logical analysis of partially ordered data in the supervised classification problem ⋮ Efficiently enumerating hitting sets of hypergraphs arising in data profiling ⋮ Unnamed Item ⋮ Finding maximal independent elements of products of partial orders (the case of chains) ⋮ Bimonotone linear inequalities and sublattices of \(\mathbb R^n\)