  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$.
