TY - JOUR
T1 - Dual-bounded generating problems
T2 - Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data
AU - Khachiyan, Leonid
AU - Boros, Endre
AU - Elbassioni, Khaled
AU - Gurvich, Vladimir
AU - Makino, Kazuhisa
N1 - Funding Information: IThis research was supported in part by the National Science Foundation (Grant IIS-0118635) and by DIMACS, the National Science Foundation’s Center for Discrete Mathematics and Theoretical Computer Science. ∗Corresponding address: Rutgers University, The State University of New Jersey, RUTCOR, 640 Bartolomew Road, 08854-8003 Piscataway, NJ, United States. Tel.: +1 7324453235; fax: +1 7324455472. E-mail addresses: boros@rutcor.rutgers.edu (E. Boros), elbassio@mpi-sb.mpg.de (K. Elbassioni), gurvich@rutcor.rutgers.edu (V. Gurvich), makino@mist.i.u-tokyo.ac.jp (K. Makino). @Our friend and co-author, Leonid Khachiyan passed away with tragic suddenness, while we were working on the final version of this paper.
PY - 2007/6/15
Y1 - 2007/6/15
N2 - We show that {divides} X {divides} ≤ n {divides} Y {divides} must hold for two finite sets X, Y ⊂ Rn whenever they can be separated by a nonnegative linear function such that X is above Y and the componentwise minimum of any two distinct points in X is dominated by some point in Y. As a consequence, we obtain an incremental quasi-polynomial time algorithm for generating all maximal integer feasible solutions for a given monotone system of separable inequalities, for generating all p-inefficient points of a given discrete probability distribution, and for generating all maximal hyper-rectangles which contain a specified fraction of points of a given set in Rn. This provides a substantial improvement over previously known exponential time algorithms for these generation problems related to Integer and Stochastic Programming, and Data Mining. Furthermore, we give an incremental polynomial time generation algorithm for monotone systems with fixed number of separable inequalities, implying that for discrete probability distributions with independent coordinates, both p-efficient and p-inefficient points can be separately generated in incremental polynomial time.
AB - We show that {divides} X {divides} ≤ n {divides} Y {divides} must hold for two finite sets X, Y ⊂ Rn whenever they can be separated by a nonnegative linear function such that X is above Y and the componentwise minimum of any two distinct points in X is dominated by some point in Y. As a consequence, we obtain an incremental quasi-polynomial time algorithm for generating all maximal integer feasible solutions for a given monotone system of separable inequalities, for generating all p-inefficient points of a given discrete probability distribution, and for generating all maximal hyper-rectangles which contain a specified fraction of points of a given set in Rn. This provides a substantial improvement over previously known exponential time algorithms for these generation problems related to Integer and Stochastic Programming, and Data Mining. Furthermore, we give an incremental polynomial time generation algorithm for monotone systems with fixed number of separable inequalities, implying that for discrete probability distributions with independent coordinates, both p-efficient and p-inefficient points can be separately generated in incremental polynomial time.
KW - Incremental generation
KW - Maximal empty boxes
KW - p-efficient points
UR - http://www.scopus.com/inward/record.url?scp=34248595484&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34248595484&partnerID=8YFLogxK
U2 - https://doi.org/10.1016/j.tcs.2007.02.044
DO - https://doi.org/10.1016/j.tcs.2007.02.044
M3 - Article
SN - 0304-3975
VL - 379
SP - 361
EP - 376
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 3
ER -