Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  An Intersection Inequality for Discrete Distributions and Related Generation Problems

Boros, E., Elbassioni, K. M., Gurvich, V., Khachiyan, L., & Makino, K. (2003). An Intersection Inequality for Discrete Distributions and Related Generation Problems. In Automata, Languages and Programming (pp. 543-555). Berlin: Springer. doi:10.1007/3-540-45061-0_44.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Boros, Endre1, Autor
Elbassioni, Khaled M.2, Autor           
Gurvich, Vladimir1, Autor
Khachiyan, Leonid1, Autor
Makino, Kazuhisa1, Autor
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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≤q 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 20032003
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: BibTex Citekey: Elbassioni2003d
DOI: 10.1007/3-540-45061-0_44
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: ICALP 2003
Veranstaltungsort: Eindhoven, The Netherlands
Start-/Enddatum: 2003-06-30 - 2003-07-04

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Automata, Languages and Programming
  Untertitel : 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 – July 4, 2003 Proceedings
  Kurztitel : ICALP 2003
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 543 - 555 Identifikator: -

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
  Kurztitel : LNCS
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 2719 Artikelnummer: - Start- / Endseite: - Identifikator: -