A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ

DOI10.1051/ro:2001120zbMath1020.90042OpenAlexW2088767615MaRDI QIDQ4546061

Márcia H. C. Fampa, Nelson F. Maculan

Publication date: 18 August 2002

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=RO_2001__35_4_383_0

zbMATH Keywords

interior point algorithmsconic formEuclidean Steiner type tree problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Interior-point methods (90C51) Combinatorial optimization (90C27)

Related Items (4)

Mixed integer nonlinear optimization models for the Euclidean Steiner tree problem in \(\mathbb{R}^d\) ⋮ Subgradient Based Outer Approximation for Mixed Integer Second Order Cone Programming ⋮ A new second‐order conic optimization model for the Euclidean Steiner tree problem in Rd$\mathbb {R}^d$ ⋮ A new heuristic for the Euclidean Steiner tree problem in \(\mathbb{R}^n\)

Cites Work

• A linear time algorithm for full Steiner trees
• How to find Steiner minimal trees in Euclidean \(d\)-space
• The Steiner tree problem
• The Euclidean Steiner tree problem in \(\mathbb{R}^{n}\): A mathematical programming formulation
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• The shortest network under a given topology
• Self-Scaled Barriers and Interior-Point Methods for Convex Programming
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• An Efficient Algorithm for Minimizing a Sum of Euclidean Norms with Applications
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Steiner Minimal Trees
• Growth conditions and \(U\)-Lagrangians

This page was built for publication: A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ