Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-2003-1-004

Improving linear programming approaches for the Steiner tree problem

Althaus, Ernst and Polzin, Tobias and Daneshmand, Siavash Vahdati

MPI-I-2003-1-004. March 2003, 19 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
We present two theoretically interesting and empirically successful
techniques for improving the linear programming approaches, namely
graph transformation and local cuts, in the context of the
Steiner problem. We show the impact of these techniques on the
solution of the largest benchmark instances ever solved.
Acknowledgement:
Categories / Keywords: Steiner problem; Lower Bounds; Linear Programming; Local Cuts
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2003-1-004.ps359 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2003-1-004
Hide details for BibTeXBibTeX
@TECHREPORT{AlthausPolzinDaneshmand2003,
  AUTHOR = {Althaus, Ernst and Polzin, Tobias and Daneshmand, Siavash Vahdati},
  TITLE = {Improving linear programming approaches for the Steiner tree problem},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2003-1-004},
  MONTH = {March},
  YEAR = {2003},
  ISSN = {0946-011X},
}