Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

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

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Polzin, Tobias
Vahdati Daneshmand, Siavash

dblp
dblp

Not MPG Author(s):

Vahdati Daneshmand, Siavash

BibTeX cite key*:

PolzinVahdati2001a

Title

Title*:

A Comparison of Steiner Tree Relaxations

Journal

Journal Title*:

Discrete Applied Mathematics

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:

http://www.elsevier.nl

Publisher's
Address:

Amsterdam, The Netherlands

ISSN:

0166-218X

Vol, No, pp, Date

Volume*:

112

Number:


Publishing Date:

August 2001

Pages*:

241-261

Number of
VG Pages:

51

Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

There are many (mixed) integer programming formulations of the Steiner problem in
networks. The corresponding linear programming relaxations are of great interest
particularly, but not exclusively, for computing lower bounds; but not much has been
known about the relative quality of these relaxations. We compare all classical and some
new relaxations from a theoretical point of view with respect to their optimal values.
Among other things, we prove that the optimal value of a flow-class relaxation (e.g. the
multicommodity flow or the dicut relaxation) cannot be worse than the optimal value of
a tree-class relaxation (e.g. degree-constrained spanning tree relaxation) and that the
ratio of the corresponding optimal values can be arbitrarily large. Furthermore, we
present a new flow based relaxation, which is to the authors' knowledge the strongest
linear relaxation of polynomial size for the Steiner problem in networks.

URL for the Abstract:


Categories,
Keywords:

Steiner Problem, Relaxation, Lower Bound

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


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:

@ARTICLE{PolzinVahdati2001a,
AUTHOR = {Polzin, Tobias and Vahdati Daneshmand, Siavash},
TITLE = {A Comparison of {Steiner} Tree Relaxations},
JOURNAL = {Discrete Applied Mathematics},
PUBLISHER = {Elsevier},
YEAR = {2001},
VOLUME = {112},
PAGES = {241--261},
ADDRESS = {Amsterdam, The Netherlands},
MONTH = {August},
ISBN = {0166-218X},
}


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 05:45:58 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Christine Kiesel
Anja Becker
Anja Becker
Tobias Polzin
Tobias Polzin
Edit Dates
26.08.2003 15:15:11
08.04.2002 15:55:56
08.04.2002 15:11:19
14/01/2002 15:17:42
06/08/2001 17:50:31
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section