# 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

top## How 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. Zbl0833.90087
- 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. Zbl0885.68088
- F.K. Hwang, A linear time algorithm for full Steiner trees. Oper. Res. Lett.4 (1986) 235-237. Zbl0582.05022
- F.K. Hwang and J.F. Weng, The shortest network under a given topology. J. Algorithms13 (1992) 468-488. Zbl0764.68119
- F.K. Hwang, D.S. Richards and P. Winter, The Steiner Tree Problem. Ann. Discrete Math.53 (1992). Zbl0774.05001
- 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). Zbl1160.90639
- N. Maculan, P. Michelon and A.E. Xavier, The Euclidean Steiner Problem in ℜ: A mathematical programming formulation. Ann. Oper. Res.96 (2000) 209-220. Zbl0966.90064
- Y.E. Nesterov and M.J. Todd, Self-Scaled Barriers and Interior-Point Methods for Convex Programming (manuscript). Zbl0871.90064
- S. Poljak, F. Rendl and H. Wolkowicz, A recipe for semidefinite relaxation for (0,1)-quadratic programming. J. Global Optim.7 (1995) 51-73. Zbl0843.90088
- W.D. Smith, How to find Steiner minimal trees in Euclidean d-space. Algorithmica7 (1992) 137-177. Zbl0751.05028
- G. Xue and Y. Ye, An Efficient Algorithm for Minimizing a Sum of Euclidean Norms with Applications. SIAM J. Optim.7 (1997) 1017-1036. Zbl0885.68074

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.