An efficient algorithm for minimizing a sum of Euclidean norms with applications

Guoliang Xue and Yinyu Ye

In this paper, the problem of minimizing a sum of Euclidean norms is studied. This problem is convex but not everywhere differentiable. By transforming the problem into a standard convex programming problem in conic form, we show that an $\epsilon$-optimal solution can be computed efficiently using interior-point algorithms. As applications to this problem, polynomial time algorithms are derived for the Euclidean single facility location problem, the Euclidean multi-facility location problem, and the shortest network under a given tree topology.

In particular, by solving the Newton equation in linear time using {\em Gaussian elimination on leaves of a tree}, we present an algorithm which computes an $\epsilon$-optimal solution to the shortest network under a given full Steiner topology interconnecting $N$ regular points, in $O(N \sqrt{N}(\log(\bar c/\epsilon)+\log N))$ arithmetic operations where $\bar c$ is the largest pair wise distance among the given points. Previous best known result on this problem is a graphical algorithm which requires $O(N^2)$ arithmetic operations under certain conditions.

University of Vermont Research Report, CSEE/95/06-01, Department of Computer Science and Electrical Engineering, The University of Vermont, June 1995.