26 września 2017 10:15
[Seminarium ZOK] Krzysztof Sornat: Ordered k-median as a generalization of k-median and k-center
Wtorek, 10:15-12:00, sala 310.
Streszczenie. k-median and k-center are well known optimization problems that were exhaustively studied in terms of approximability. There exits 2-approximation algorithm for k-center problem and it is NP-hard to approximate the problem with the factor less than 2. For k-median there was a lot of algorithmic techniques developed for achieving better approximation ratios. Still there is a gap between hardness results and known approximation algorithms (2.675-apx).
We study a problem called Ordered k-median that is a generalization of both k-median and k-center. In Ordered k-median additionaly we are given a sequence of non-increasing weights (w_1, w_2, ... , w_n). We want to find k facilities to open such that we minimize sum of weighted connection costs where the highest weight is applied to the highest connection cost. k-median problem is a special case of Ordered k-median with weights (1, 1, ... , 1). k-center problem is a special case of Ordered k-median with weights (1, 0, ... , 0).
It was known that we can approximate Ordered k-median problem within factor O(log(n)) for general weights in polynomial time. We provide a constant factor approximation algorithm for special case called "one rectangle" that has a sequence of weights equal to 1's and 0's (k-median and k-center are included in that). For that we guess some treshold to change the cost function and we use adapted Charikar-Li dependent LP-rounding approach. We use this special case to solve the problem with general weights giving constant factor approximation algorithm for Ordered k-median in pseudo-polynomial time i.e. O(n^log(n)).
Joint work with Jarosław Byrk and Joachim Spoerhase.