Solving convex location problems with gauges in polynomial time

An interior point algorithm for solving continuous single- or multi- facility location problems is presented. Distances can be measured with arbitrary, possibly nonsymmetric gauges, while the globalizing function value is assumed to be a convex quadratic and monotonically nondecreasing function. Using the notion of self-concordant barrier functions, it is shown that the algorithm computes an epsilon-approximation to the minimum of the objective function with a number of floating point operations which is bounded by a polynomial in the input size and log(1/ϵ). The algorithm can be extended to the case in which the globalizing function contains additionally the maximum