##
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.