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

DOI10.1016/J.TCS.2007.02.044MaRDI QIDQ2373724zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• scientific article; zbMATH DE number 2038737
• Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
• scientific article; zbMATH DE number 1754587
• Mathematical Foundations of Computer Science 2005
• Dual-bounded generating problems: Partial and multiple transversals of a hypergraph

Cites work

• A new algorithm for the largest empty rectangle problem
• A note on finding a maximum empty rectangle
• Complexity of identification and dualization of positive Boolean functions
• Computing the Largest Empty Rectangle
• Concavity and efficient points of discrete distributions in probabilistic programming.
• Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
• Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
• scientific article; zbMATH DE number 41082 (Why is no real title available?)
• scientific article; zbMATH DE number 2080472 (Why is no real title available?)
• scientific article; zbMATH DE number 772850 (Why is no real title available?)
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the maximum empty rectangle problem
• The Maximum Latency and Identification of Positive Boolean Functions

Cited in

(6)

• Lower bounds for three algorithms for transversal hypergraph generation
• Computing the probability of union in the $n$-dimensional Euclidean space for application of the multivariate quantile: $p$-level efficient points
• scientific article; zbMATH DE number 2038737 (Why is no real title available?)
• Dual bounded generation: polynomial, second-order cone and positive semidefinite matrix inequalities
• Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions
• Scientific contributions of Leo Khachiyan (a short overview)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373724)