[Back]

J. Chen, D. Hermelin, M. Sorge:
"Computational aspects of multiwinner approval voting via p-norm Hamming distance vectors";
Talk: Aggregation across disciplines: connections and frameworks, Paris (invited); 2021-12-15 - 2021-12-17.

We consider a family of multiwinner approval voting rules, which generalize the classical minisum and minimax procedures. Specifically, given a rational number p and approval ballots, the p-norm Hamming rule chooses a subset of co-winners which minimizes the p-norm of the vector of Hamming distances (i.e., the sizes of the symmetric differences) to the ballots. The minisum and minimax procedures are hence special cases and correspond to p = 1 and p = ∞, respectively. It is well-known that determining a winner set under the minisum procedure (p = 1) can be done in polynomial time, while it becomes NP-hard under the minimax procedure (p = ∞). In this work, we show that winner determination remains NP-hard for every fixed rational p > 1, closing the gap for all rational values of p between 1 and infinity. We also provide an almost tight exponential-time algorithm and a simple factor-2 approximation algorithm for all fixed p > 1.