Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data

DOI10.1016/j.tcs.2007.02.044zbMath1115.68105OpenAlexW2000597930MaRDI QIDQ2373724

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

Publication date: 16 July 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.044

zbMATH Keywords

\(p\)-efficient pointsincremental generationmaximal empty boxes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Related Items (2)

Scientific contributions of Leo Khachiyan (a short overview) ⋮ Lower bounds for three algorithms for transversal hypergraph generation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new algorithm for the largest empty rectangle problem
• On the maximum empty rectangle problem
• A note on finding a maximum empty rectangle
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• Complexity of identification and dualization of positive Boolean functions
• Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph
• Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
• Computing the Largest Empty Rectangle
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• The Maximum Latency and Identification of Positive Boolean Functions
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• Concavity and efficient points of discrete distributions in probabilistic programming.

This page was built for publication: Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data