MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Polzin, Tobias
Vahdati Daneshmand, Siavash
dblp
dblp
Not MPG Author(s):
Vahdati Daneshmand, Siavash
Editor(s):
Jansen, Klaus
Khuller, Samir
dblp
dblp
Not MPII Editor(s):
Jansen, Klaus
Khuller, Samir
BibTeX cite key*:
PolzinVahdati2000
Title, Booktitle
Title*:
Primal-Dual Approaches to the Steiner Problem
Booktitle*:
Approximation Algorithms for Combinatorial Optimization
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Saarbrücken, Germany
Language:
English
Event Date*
(no longer used):
September 2000
Organization:
Event Start Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Event End Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1913
Number:
Month:
Pages:
214-225
Year*:
2000
VG Wort Pages:
26
ISBN/ISSN:
3-540-67996-0
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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)$.
Keywords:
Steiner Problem, Relaxation, Lower Bound, Approximation
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{PolzinVahdati2000,
AUTHOR = {Polzin, Tobias and Vahdati Daneshmand, Siavash},
EDITOR = {Jansen, Klaus and Khuller, Samir},
TITLE = {Primal-Dual Approaches to the Steiner Problem},
BOOKTITLE = {Approximation Algorithms for Combinatorial Optimization},
PUBLISHER = {Springer},
YEAR = {2000},
VOLUME = {1913},
PAGES = {214--225},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Saarbr{\"u}cken, Germany},
ISBN = {3-540-67996-0},
}


Entry last modified by Christine Kiesel, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Andreas Polzin
Created
08/06/2001 06:20:36 PM
Revisions
2.
1.
0.

Editor(s)
Christine Kiesel
Tobias Polzin
Andreas Polzin

Edit Dates
26.08.2003 15:16:03
14/01/2002 15:52:54
06/08/2001 18:20:36