  We study a generic framework that provides a unified view on two important
classes of problems: (i) extensions of the k-median problem where clients are
interested in having multiple facilities in their vicinity (e.g., due to the
fact that, with some small probability, the closest facility might be
malfunctioning and so might not be available for using), and (ii) finding
winners according to some appealing multiwinner election rules, i.e., election
system aimed for choosing representatives bodies, such as parliaments, based on
preferences of a population of voters over individual candidates. Each problem
in our framework is associated with a vector of weights: we show that the
approximability of the problem depends on structural properties of these
vectors. We specifically focus on the harmonic sequence of weights for which
the objective function interpreted in a multiwinner election setup reflects to
the well-known Proportional Approval Voting (PAV) rule.
  Our main result is that, due to the specific (harmonic) structure of weights,
the problem allows constant factor approximation. This is surprising since the
problem can be interpreted as a variant of the k-median problem where we do not
assume that the connection costs satisfy the triangle inequality. The algorithm
we propose is based on dependent rounding [Srinivasan, FOCS'01] applied to the
solution of a natural LP-relaxation of the problem. The rounding process is
well known to produce distributions over integral solutions satisfying Negative
Correlation (NC), which is usually sufficient for the analysis of approximation
guarantees offered by rounding procedures. In our analysis, however, we need to
use the fact that the carefully implemented rounding process satisfies a
stronger property, called Negative Association (NA), which allows us to apply
standard concentration bounds for conditional random variables.
