Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  A Comparison of Steiner Tree Relaxations

Polzin, T., & Vahdati Daneshmand, S. (2001). A Comparison of Steiner Tree Relaxations. Discrete Applied Mathematics, 112, 241-261.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3158-8 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3159-6
Genre: Zeitschriftenartikel

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Polzin, Tobias1, Autor           
Vahdati Daneshmand, Siavash, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-022001
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 518183
Anderer: Local-ID: C1256428004B93B8-8CF3299D5600FB3DC1256AA000569B54-PolzinVahdati2001a
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Discrete Applied Mathematics
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 112 Artikelnummer: - Start- / Endseite: 241 - 261 Identifikator: ISSN: 0166-218X