Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  Robustness analysis in combinatorial optimization

Frederickson, G. N., & Solis-Oba, R.(1998). Robustness analysis in combinatorial optimization (MPI-I-1998-1-011). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
MPI-I-98-1-011.pdf (beliebiger Volltext), 504KB
Name:
MPI-I-98-1-011.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Frederickson, Greg N.1, Autor
Solis-Oba, Roberto2, Autor           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: The robustness function of an optimization problem measures the maximum change in the value of its optimal solution that can be produced by changes of a given total magnitude on the values of the elements in its input. The problem of computing the robustness function of matroid optimization problems is studied under two cost models: the discrete model, which allows the removal of elements from the input, and the continuous model, which permits finite changes on the values of the elements in the input. For the discrete model, an $O(\log k)$-approximation algorithm is presented for computing the robustness function of minimum spanning trees, where $k$ is the number of edges to be removed. The algorithm uses as key subroutine a 2-approximation algorithm for the problem of dividing a graph into the maximum number of components by removing $k$ edges from it. For the continuous model, a number of results are presented. First, a general algorithm is given for computing the robustness function of any matroid. The algorithm runs in strongly polynomial time on matroids with a strongly polynomial time independence test. Faster algorithms are also presented for some particular classes of matroids: (1) an $O(n^3m^2 \log (n^2/m))$-time algorithm for graphic matroids, where $m$ is the number of elements in the matroid and $n$ is its rank, (2) an $O(mn(m+n^2)|E|\log(m^2/|E|+2))$-time algorithm for transversal matroids, where $|E|$ is a parameter of the matroid, (3) an $O(m^2n^2)$-time algorithm for scheduling matroids, and (4) an $O(m \log m)$-time algorithm for partition matroids. For this last class of matroids an optimal algorithm is also presented for evaluating the robustness function at a single point.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 1998
 Publikationsstatus: Erschienen
 Seiten: 66 p.
 Ort, Verlag, Ausgabe: Saarbrücken : Max-Planck-Institut für Informatik
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: Reportnr.: MPI-I-1998-1-011
BibTex Citekey: FredericksonSolis-Oba98
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Research Report / Max-Planck-Institut für Informatik
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: - Identifikator: -