Approximating Star Cover Problems
share
Given a metric space (F ∪ C, d), we consider star covers of C with balanced loads. A star is a pair (f, C_f) where f ∈ F and C_f ⊆ C, and the load of a star is ∑_c ∈ C_f d(f, c). In minimum load k-star cover problem (MLkSC), one tries to cover the set of clients C using k stars that minimize the maximum load of a star, and in minimum size star cover (MSSC) one aims to find the minimum number of stars of load at most T needed to cover C, where T is a given parameter. We obtain new bicriteria approximations for the two problems using novel rounding algorithms for their standard LP relaxations. For MLkSC, we find a star cover with (1+ε)k stars and O(1/ε^2)OPT_MLk load where OPT_MLk is the optimum load. For MSSC, we find a star cover with O(1/ε^2) OPT_MS stars of load at most (2 + ε) T where OPT_MS is the optimal number of stars for the problem. Previously, non-trivial bicriteria approximations were known only when F = C.
READ FULL TEXT