Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Primal-Dual Approaches to the Steiner Problem

Polzin, T., & Vahdati Daneshmand, S. (2000). Primal-Dual Approaches to the Steiner Problem. In K. Jansen, & S. Khuller (Eds.), Approximation Algorithms for Combinatorial Optimization (pp. 214-225). Berlin, Germany: Springer.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-33F1-D Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-33F3-9
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Polzin, Tobias1, Autor           
Vahdati Daneshmand, Siavash, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We study several old and new algorithms for computing lower and upper bounds for the Steiner problem in networks using dual-ascent and primal-dual strategies. We show that none of the known algorithms can both generate tight lower bounds empirically and guarantee their quality theoretically; and we present a new algorithm which combines both features. The new algorithm has running time $O(re\log n)$ and guarantees a ratio of at most two between the generated upper and lower bounds, whereas the fastest previous algorithm with comparably tight empirical bounds has running time $O(e^2)$ without a constant approximation ratio. Furthermore, we show that the approximation ratio two between the bounds can even be achieved in time $O(e + n\log n)$, improving the previous time bound of $O(n^2\log n)$.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-022000
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 518185
Anderer: Local-ID: C1256428004B93B8-AAACDA30D457F04FC1256AA00059C715-PolzinVahdati2000
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Saarbrücken, Germany
Start-/Enddatum: -

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Approximation Algorithms for Combinatorial Optimization
Genre der Quelle: Konferenzband
 Urheber:
Jansen, Klaus1, Herausgeber           
Khuller, Samir, Herausgeber
Affiliations:
1 Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019            
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 214 - 225 Identifikator: ISBN: 3-540-67996-0

Quelle 2

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