Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  An Inequality for Polymatroid Functions and its Applications

Boros, E., Elbassioni, K. M., Khachiyan, L., & Gurvich, V. (2003). An Inequality for Polymatroid Functions and its Applications. Discrete applied mathematics, 131, 27.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
ineq-poly.pdf (beliebiger Volltext), 315KB
 
Datei-Permalink:
-
Name:
ineq-poly.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

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

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: An integral-valued set function f:2^V \mapsto \ZZ is called polymatroid if it is submodular, non-decreasing, and f(\emptyset)=0. Given a polymatroid function f and an integer threshold t≥q 1, let α=α(f,t) denote the number of maximal sets X \subseteq V satisfying f(X) < t, let β=β(f,t) be the number of minimal sets X \subseteq V for which f(X) ≥ t, and let n=|V|. We show that if β ≥ 2 then α ≤ β^(\log t)/c}, where c=c(n,β) is the unique positive root of the equation 1=2^c(n^{c/\logβ}-1). In particular, our bound implies that α ≤ (nβ)^{\log t} for all β ≥ 1. We also give examples of polymatroid functions with arbitrarily large t, n, α and β for which α ≥ β^{(.551 \log t)/c}. More generally, given a polymatroid function f:2^V \mapsto \ZZ and an integral threshold t ≥ 1, consider an arbitrary hypergraph \cH such that |\cH| ≥ 2 and f(H) ≥ t for all H \in \cH. Let \cS be the family of all maximal independent sets X of \cH for which f(X) <t. Then |\cS| ≤q |\cH|^{(\log t)/c(n,|\cH|). As an application, we show that given a system of polymatroid inequalities f_1(X) ≥ t_1,\ldots,f_m(X) ≥ t_m with quasi-polynomially bounded right hand sides t_1,\ldots,t_m, all minimal feasible solutions to this system can be generated in incremental quasi-polynomial time. In contrast to this result, the generation of all maximal infeasible sets is an NP-hard problem for many polymatroid inequalities of small range.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2003
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: BibTex Citekey: Elbassioni2003a
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Discrete applied mathematics
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Amsterdam : North-Holland
Seiten: - Band / Heft: 131 Artikelnummer: - Start- / Endseite: 27 Identifikator: ISSN: 0166-218X
CoNE: https://pure.mpg.de/cone/journals/resource/954925482629