CS Forum: "Constant-Factor Approximation for Ordered k-Median" Joachim Spoerhase, Universität Würzburg

CS department's public guest lecture, open to everyone free-of-charge.

Joachim Spoerhase
Universität Würzburg, Germany

Host: Prof Parinya Chalermsook
Time: 14:15 (coffee at 14:00)
Venue: T5, CS building

Constant-Factor Approximation for Ordered k-Median

Abstract:

We study the Ordered k-Median problem, in which the solution is evaluated by first sorting the client connection costs and then multiplying them with a predefined non-increasing weight vector (higher connection costs are taken with larger weights). The problem unifies many fundamental clustering and location problems such as k-Median and k-Center. This generality, however, renders the problem intriguing from the algorithmic perspective. Recently, Aouad and Segev proposed a sophisticated local-search based O(log n) approximation algorithm for general weight vectors, extending the result by Tamir (2001) for the case of a rectangular weight vector, also known as k-Facility p-Centrum. The existence of a constant-factor approximation algorithm remained open, even for the special case with a rectangular weight vector.

Our main result is an LP-rounding constant-factor approximation algorithm for the Ordered k-Median problem with general weight vectors.

We first provide a new analysis of the rounding process by Charikar and Li (2012) for k-Median, when applied to a fractional solution obtained from solving an LP with a carefully modified objective function, results in an elegant 15-approximation for the rectangular case. In our analysis, the connection cost of a single client is partly charged to a deterministic budget related to a combinatorial bound based on guessing, and partly to a budget whose expected value is bounded with respect to the fractional LP-solution. This approach allows to limit the problematic effect of the variance of individual client connection costs on the value of the ordered objective function of the Ordered k-Median problem. Next we analyze objective-oblivious clustering that allows to handle multiple rectangles in the weight vector and obtain constant factor approximation for the case of O(1) rectangles. Then, we show that a simple weight bucketing can be applied to general weight vectors resulting in O(log n) rectangles and hence in a constant factor approximation in quasi-polynomial time. Finally, with a more involved argument, we show that also the clever distance bucketing by Aouad and Segev can be combined with the objective-oblivious version of our LP-rounding for the rectangular case, and that it results in a true, polynomial time, constant-factor approximation algorithm.

This work was accepted to STOC 2018.