# A new relaxation in conic form for the euclidean Steiner problem in ${\Re}^{n}$

RAIRO - Operations Research - Recherche Opérationnelle (2001)

- 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 $\Re ^n$." RAIRO - Operations Research - Recherche Opérationnelle 35.4 (2001): 383-394. <http://eudml.org/doc/105252>.

@article{Fampa2001,

abstract = {In this paper, we present a new mathematical programming formulation for the euclidean Steiner Tree Problem (ESTP) in $\Re ^n$. 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 $\epsilon $-optimal solution for this latter problem using interior-point algorithm.},

author = {Fampa, Marcia, Maculan, Nelson},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {euclidean Steiner tree problem; conic form; interior point algorithms; Euclidean Steiner type tree problem},

language = {eng},

number = {4},

pages = {383-394},

publisher = {EDP-Sciences},

title = {A new relaxation in conic form for the euclidean Steiner problem in $\Re ^n$},

url = {http://eudml.org/doc/105252},

volume = {35},

year = {2001},

}

TY - JOUR

AU - Fampa, Marcia

AU - Maculan, Nelson

TI - A new relaxation in conic form for the euclidean Steiner problem in $\Re ^n$

JO - RAIRO - Operations Research - Recherche Opérationnelle

PY - 2001

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 $\Re ^n$. 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 $\epsilon $-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

UR - http://eudml.org/doc/105252

ER -

## References

top- [1] F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5 (1995) 13-51. Zbl0833.90087MR1315703
- [2] E.N. Gilbert and H.O. Pollack, Steiner minimal trees. SIAM J. Appl. Math. 16 (1968) 323-345. Zbl0159.22001MR223269
- [3] M.X. Goemans and D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 6 (1995) 1115-1145. Zbl0885.68088MR1412228
- [4] F.K. Hwang, A linear time algorithm for full Steiner trees. Oper. Res. Lett. 4 (1986) 235-237. Zbl0582.05022MR829887
- [5] F.K. Hwang and J.F. Weng, The shortest network under a given topology. J. Algorithms 13 (1992) 468-488. Zbl0764.68119MR1176673
- [6] F.K. Hwang, D.S. Richards and P. Winter, The Steiner Tree Problem. Ann. Discrete Math. 53 (1992). Zbl0774.05001MR1192785
- [7] 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
- [8] N. Maculan, P. Michelon and A.E. Xavier, The Euclidean Steiner Problem in ${\Re}^{n}$: A mathematical programming formulation. Ann. Oper. Res. 96 (2000) 209-220. Zbl0966.90064MR1802523
- [9] Y.E. Nesterov and M.J. Todd, Self-Scaled Barriers and Interior-Point Methods for Convex Programming (manuscript). Zbl0871.90064
- [10] 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.90088MR1342935
- [11] W.D. Smith, How to find Steiner minimal trees in Euclidean $d$-space. Algorithmica 7 (1992) 137-177. Zbl0751.05028MR1146493
- [12] 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.68074MR1479612

## NotesEmbed ?

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