Approximation Algorithms for BalancedCC Multiwinner Rules

X-BalancedCC multiwinner voting rules constitute an attractive but computationally intractable compromise between the proportionality provided by the Monroe rule and the diversity provided by the Chamberlin-Courant rule. We show how to use the Greedy-Monroe algorithm to get improved approximation results for the X-BalancedCC rules and for the Chamberlin-Courant rule, by appropriately setting a "schedule" for the sizes of virtual districts. We describe a polynomial-time algorithm for computing a schedule that guarantees high approximation ratio, but show that finding the best possible schedule for a given election is NP-hard. We further evaluate our algorithms experimentally and show that they perform very well in practice.