Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:


URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section