  We consider the algorithmic question of choosing a subset of candidates of a
given size $k$ from a set of $m$ candidates, with knowledge of voters' ordinal
rankings over all candidates. We consider the well-known and classic scoring
rule for achieving diverse representation: the Chamberlin-Courant (CC) or
$1$-Borda rule, where the score of a committee is the average over the voters,
of the rank of the best candidate in the committee for that voter; and its
generalization to the average of the top $s$ best candidates, called the
$s$-Borda rule.
  Our first result is an improved analysis of the natural and well-studied
greedy heuristic. We show that greedy achieves a $\left(1 -
\frac{2}{k+1}\right)$-approximation to the maximization (or satisfaction)
version of CC rule, and a $\left(1 - \frac{2s}{k+1}\right)$-approximation to
the $s$-Borda score. Our result improves on the best known approximation
algorithm for this problem. We show that these bounds are almost tight.
  For the dissatisfaction (or minimization) version of the problem, we show
that the score of $\frac{m+1}{k+1}$ can be viewed as an optimal benchmark for
the CC rule, as it is essentially the best achievable score of any
polynomial-time algorithm even when the optimal score is a polynomial factor
smaller (under standard computational complexity assumptions). We show that
another well-studied algorithm for this problem, called the Banzhaf rule,
attains this benchmark.
  We finally show that for the $s$-Borda rule, when the optimal value is small,
these algorithms can be improved by a factor of $\tilde \Omega(\sqrt{s})$ via
LP rounding. Our upper and lower bounds are a significant improvement over
previous results, and taken together, not only enable us to perform a finer
comparison of greedy algorithms for these problems, but also provide analytic
justification for using such algorithms in practice.
