MPI-INF D1 Publications: Journal Article: A Comparison of {Steiner} Tree Relaxations

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2022) | last year (2021) | two years ago (2020) | Notes URL

Action:

Options:

Goto entry point

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

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

Attachment Section