Home News About Us Contact Contributors Disclaimer Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Display Documents



ID: 518185.0, MPI für Informatik / Algorithms and Complexity Group
Primal-Dual Approaches to the Steiner Problem
Authors:Polzin, Tobias; Vahdati Daneshmand, Siavash
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2000
Title of Proceedings:Approximation Algorithms for Combinatorial Optimization
Start Page:214
End Page:225
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Saarbrücken, Germany
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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)$.
Last Change of the Resource (YYYY-MM-DD):2010-03-02
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-AAACDA30D457F04FC1256AA00059C715-...
ISBN:3-540-67996-0
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.