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

Guoliang Xue and Yinyu Ye

In recent years rich theories on polynomial time interior-point algorithms have been developed. These theories and algorithms can be applied to many nonlinear optimization problems to yield better complexity results for various applications.

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.