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

Leonid Khachiyan, Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

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.

Original languageEnglish (US)
Pages (from-to)361-376
Number of pages16
JournalTheoretical Computer Science
Volume379
Issue number3
DOIs
StatePublished - Jun 15 2007

Fingerprint

Multidimensional Data
Discrete Distributions
Probability distributions
Probability Distribution
Polynomials
Divides
Monotone Systems
Stochastic programming
Integer programming
Polynomial time
Data mining
Stochastic Programming
Exponential time
Integer Programming
Rectangle
Linear Function
Polynomial-time Algorithm
Finite Set
Data Mining
Non-negative

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Incremental generation
  • Maximal empty boxes
  • p-efficient points

Cite this

@article{a28e73501b464fefbe97bd23a874c5b7,
title = "Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data",
abstract = "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.",
keywords = "Incremental generation, Maximal empty boxes, p-efficient points",
author = "Leonid Khachiyan and Endre Boros and Khaled Elbassioni and Vladimir Gurvich and Kazuhisa Makino",
year = "2007",
month = "6",
day = "15",
doi = "https://doi.org/10.1016/j.tcs.2007.02.044",
language = "English (US)",
volume = "379",
pages = "361--376",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "3",

}

Dual-bounded generating problems : Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data. / Khachiyan, Leonid; Boros, Endre; Elbassioni, Khaled; Gurvich, Vladimir; Makino, Kazuhisa.

In: Theoretical Computer Science, Vol. 379, No. 3, 15.06.2007, p. 361-376.

Research output: Contribution to journalArticle

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

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

VL - 379

SP - 361

EP - 376

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 3

ER -