An intersection inequality for discrete distributions and related generation problems

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

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

14 Scopus citations

Abstract

Given two finite sets of points X, Y in ℝn which can be separated by a nonnegative linear function, and such that the componentwise minimum of any two distinct points in X is dominated by some point in Y, we show that |X| ≤ n|Y|. As a consequence of this result, we obtain quasi-polynomial time algorithms 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 empty hyper-rectangles for a given set of points in ℝn. This provides a substantial improvement over previously known exponential 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, which, for the very special case of one inequality, implies that for discrete probability distributions with independent coordinates, both p-efficient and p-inefficient points can be separately generated in incremental polynomial time.

Original languageBritish English
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsJos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Woeginger
PublisherSpringer Verlag
Pages543-555
Number of pages13
ISBN (Print)3540404937, 9783540404934
DOIs
StatePublished - 2003

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2719
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Dive into the research topics of 'An intersection inequality for discrete distributions and related generation problems'. Together they form a unique fingerprint.

Cite this