A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ
RAIRO - Operations Research (2010)
- Volume: 35, Issue: 4, page 383-394
- ISSN: 0399-0559
Access Full Article
top
Abstract
topHow to cite
topFampa, Marcia, and Maculan, Nelson. "A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ ." RAIRO - Operations Research 35.4 (2010): 383-394. <http://eudml.org/doc/197792>.
@article{Fampa2010,
abstract = {
In this paper, we present a
new mathematical programming formulation for the Euclidean Steiner
Tree Problem (ESTP) in ℜ. We relax the integrality
constrains on this formulation and transform the resulting
relaxation, which is convex, but not everywhere differentiable,
into a standard convex programming problem in conic form. We
consider then an efficient computation of an ϵ-optimal
solution for this latter problem using interior-point algorithm.
},
author = {Fampa, Marcia, Maculan, Nelson},
journal = {RAIRO - Operations Research},
keywords = {Euclidean Steiner tree problem; conic
form; interior point algorithms.; Euclidean Steiner type tree problem; conic form; interior point algorithms},
language = {eng},
month = {3},
number = {4},
pages = {383-394},
publisher = {EDP Sciences},
title = {A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ },
url = {http://eudml.org/doc/197792},
volume = {35},
year = {2010},
}
TY - JOUR
AU - Fampa, Marcia
AU - Maculan, Nelson
TI - A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ
JO - RAIRO - Operations Research
DA - 2010/3//
PB - EDP Sciences
VL - 35
IS - 4
SP - 383
EP - 394
AB -
In this paper, we present a
new mathematical programming formulation for the Euclidean Steiner
Tree Problem (ESTP) in ℜ. We relax the integrality
constrains on this formulation and transform the resulting
relaxation, which is convex, but not everywhere differentiable,
into a standard convex programming problem in conic form. We
consider then an efficient computation of an ϵ-optimal
solution for this latter problem using interior-point algorithm.
LA - eng
KW - Euclidean Steiner tree problem; conic
form; interior point algorithms.; Euclidean Steiner type tree problem; conic form; interior point algorithms
UR - http://eudml.org/doc/197792
ER -
References
top- F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim.5 (1995) 13-51.
- E.N. Gilbert and H.O. Pollack, Steiner minimal trees. SIAM J. Appl. Math.16 (1968) 323-345.
- M.X. Goemans and D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM6 (1995) 1115-1145.
- F.K. Hwang, A linear time algorithm for full Steiner trees. Oper. Res. Lett.4 (1986) 235-237.
- F.K. Hwang and J.F. Weng, The shortest network under a given topology. J. Algorithms13 (1992) 468-488.
- F.K. Hwang, D.S. Richards and P. Winter, The Steiner Tree Problem. Ann. Discrete Math.53 (1992).
- C. Lemaréchal and F. Oustry, Semidefinite relaxations and Lagrangian duality with application to combinatorial optimization. Rapport de recherche, Institut National de Recherche en Informatique et en Automatique, INRIA (1999).
- N. Maculan, P. Michelon and A.E. Xavier, The Euclidean Steiner Problem in ℜ: A mathematical programming formulation. Ann. Oper. Res.96 (2000) 209-220.
- Y.E. Nesterov and M.J. Todd, Self-Scaled Barriers and Interior-Point Methods for Convex Programming (manuscript).
- S. Poljak, F. Rendl and H. Wolkowicz, A recipe for semidefinite relaxation for (0,1)-quadratic programming. J. Global Optim.7 (1995) 51-73.
- W.D. Smith, How to find Steiner minimal trees in Euclidean d-space. Algorithmica7 (1992) 137-177.
- G. Xue and Y. Ye, An Efficient Algorithm for Minimizing a Sum of Euclidean Norms with Applications. SIAM J. Optim.7 (1997) 1017-1036.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.