Abstract We study the complexity of determining a winning committee under the Chamberlin–Courant voting rule when voters’ preferences are single-crossing on a line, or, more generally, on a median graph (this class of graphs includes, e. g. , trees and grids). For the line, Skowron et al. (2015) describe an O (n^2mk) O (n 2 mk) algorithm (where n n, m m, k k are the number of voters, the number of candidates and the committee size, respectively) ; we show that a simple tweak improves the time complexity to O (nmk) O (n m k). We then improve this bound even further by reducing our problem to the k k -link path problem for complete DAGs with Monge-concave weights, obtaining an O (n^1 + o (1) m) O (n 1 + o (1) m) algorithm for arbitrary misrepresentation functions and a nearly linear algorithm for the Borda misrepresentation function. For trees, we point out an issue with the algorithm proposed by Clearwater et al. (2015), and develop an O (nmk) O (n m k) algorithm for this case as well. For grids, we formulate a conjecture about the structure of optimal solutions, and describe a polynomial-time algorithm that finds a winning committee if this conjecture is true; we also explain how to convert this algorithm into a bicriterial approximation algorithm whose correctness does not depend on the conjecture.
Constantinescu et al. (Tue,) studied this question.