Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor
 Author(s): Boros, Endre Elbassioni, Khaled M. Gurvich, Vladimir Khachiyan, Leonid Makino, Kazuhisa dblp dblp dblp dblp dblp Not MPG Author(s): Boros, Endre Gurvich, Vladimir Khachiyan, Leonid Makino, Kazuhisa
 Editor(s):
 BibTeX cite key*: Elbassioni2003d

 Title, Booktitle
 Title*: An Intersection Inequality for Discrete Distributions and Related Generation Problems ICALP03.pdf (198.12 KB) Booktitle*: Automata, Languages and Programming, 30th International Colloquium, ICALP 2003

 Event, URLs
 URL of the conference: URL for downloading the paper: Event Address*: Eindhoven, The Netherlands Language: English Event Date* (no longer used): Organization: Event Start Date: 30 June 2003 Event End Date: 4 July 2003

 Publisher
 Name*: Springer URL: Address*: Berlin, Germany Type:

 Vol, No, Year, pp.
 Series: Lecture Notes in Computer Science
 Volume: 2719 Number: Month: June Pages: 543-555 Year*: 2003 VG Wort Pages: ISBN/ISSN: Sequence Number: DOI:

 (LaTeX) Abstract: Given two finite sets of points ${\mathcal X},{\mathcal Y}$ in ${\mathbb{R}}^n$ which can be separated by a nonnegative linear function, and such that the componentwise minimum of any two distinct points in ${\mathcal X}$ is dominated by some point in ${\mathcal Y}$, we show that $\vert{\mathcal X}\vert\leq n\vert{\mathcal Y}\vert$. 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 ${\mathbb{R}}^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. Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{Elbassioni2003d,
AUTHOR = {Boros, Endre and Elbassioni, Khaled M. and Gurvich, Vladimir and Khachiyan, Leonid and Makino, Kazuhisa},
TITLE = {An Intersection Inequality for Discrete Distributions and Related Generation Problems},
BOOKTITLE = {Automata, Languages and Programming, 30th International Colloquium, ICALP 2003},
PUBLISHER = {Springer},
YEAR = {2003},
VOLUME = {2719},
PAGES = {543--555},
SERIES = {Lecture Notes in Computer Science},