Given a metric space $(F \cup C, d)$, we consider star covers of $C$ with balanced loads. A star is a pair $(f, C_f)$ where $f \in F$ and $C_f \subseteq C$, and the load of a star is $\sum_{ c \in C_f} d(f, c)$. In minimum load $k$-star cover problem $(\mathrm{ 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 $(\mathrm{ 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 $\mathrm{ MLkSC}$, we find a star cover with $(1+\varepsilon)k$ stars and $O(1/\varepsilon^2)\mathrm{ OPT}_{ \mathrm{ MLk}}$ load where $\mathrm{ OPT}_{ \mathrm{ MLk}}$ is the optimum load. For $\mathrm{ MSSC}$, we find a star cover with $O(1/\varepsilon^2) \mathrm{ OPT}_{ \mathrm{ MS}}$ stars of load at most $(2 + \varepsilon) T$ where $\mathrm{ OPT}_{ \mathrm{ MS}}$ is the optimal number of stars for the problem. Previously, non-trivial bicriteria approximations were known only when $F = C$.
Categories: cs.DS