Primal-Dual Approaches to the Steiner Problem

Local TagsStatisticsRevisionsRelease HistoryDetails

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 Released

show all hide all

Basic

show hide

Bookmark this item: http://pubman.mpdl.mpg.de/pubman/item/escidoc:1330884:2

Genre: Conference Paper

Files

show Files

Locators

show

Creators

show

hide

Creators:
Polzin, Tobias¹, Author
Vahdati Daneshmand, Siavash, Author

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, escidoc:24019

Content

show

hide

Free keywords: -

Abstract: 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

show

hide

Language(s): eng - English

Dates: Modified: 2010-03-02 Published in Print: 2000

Pages: -

Publishing info: -

Table of Contents: -

Rev. Method: -

Identifiers: eDoc: 518185
Other: Local-ID: C1256428004B93B8-AAACDA30D457F04FC1256AA00059C715-PolzinVahdati2000

Degree: -

Event

show

hide

Title: Untitled Event

Place of Event: Saarbrücken, Germany

Start-/End Date: -

Legal Case

show

Source 1

show

hide

Title: Approximation Algorithms for Combinatorial Optimization

Source Genre: Proceedings

Creator(s):
Jansen, Klaus¹, Editor
Khuller, Samir, Editor

Affiliations:
1 Algorithms and Complexity, MPI for Informatics, Max Planck Society, escidoc:24019

Publ. Info: Berlin, Germany : Springer

Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 214 - 225 Identifier: ISBN: 3-540-67996-0

Source 2

show

hide

Title: Lecture Notes in Computer Science

Source Genre: Series

Creator(s):
-

Affiliations:
-

Publ. Info: -

Pages: - Volume / Issue: 1913 Sequence Number: - Start / End Page: - Identifier: -