2026-07-23T22:19:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22213 2024-12-05T15:18:03Z ddc:004 open_access

When Far Is Better: The Chamberlin-Courant Approach to Obnoxious Committee Selection Gupta, Sushmita Inamdar, Tanmay Jain, Pallavi Lokshtanov, Daniel Panolan, Fahad Saurabh, Saket Metric Space Parameterized Complexity Approximation Obnoxious Facility Location Classical work on metric space based committee selection problem interprets distance as "near is better". In this work, motivated by real-life situations, we interpret distance as "far is better". Formally stated, we initiate the study of "obnoxious" committee scoring rules when the voters' preferences are expressed via a metric space. To accomplish this, we propose a model where large distances imply high satisfaction (in contrast to the classical setting where shorter distances imply high satisfaction) and study the egalitarian avatar of the well-known Chamberlin-Courant voting rule and some of its generalizations. For a given integer value λ between 1 and k, the committee size, a voter derives satisfaction from only the λth favorite committee member; the goal is to maximize the satisfaction of the least satisfied voter. For the special case of λ = 1, this yields the egalitarian Chamberlin-Courant rule. In this paper, we consider general metric space and the special case of a d-dimensional Euclidean space. We show that when λ is 1 and k, the problem is polynomial-time solvable in ℝ² and general metric space, respectively. However, for λ = k-1, it is NP-hard even in ℝ². Thus, we have "double-dichotomy" in ℝ² with respect to the value of λ, where the extreme cases are solvable in polynomial time but an intermediate case is NP-hard. Furthermore, this phenomenon appears to be "tight" for ℝ² because the problem is NP-hard for general metric space, even for λ = 1. Consequently, we are motivated to explore the problem in the realm of (parameterized) approximation algorithms and obtain positive results. Interestingly, we note that this generalization of Chamberlin-Courant rules encodes practical constraints that are relevant to solutions for certain facility locations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sushmita Gupta and Tanmay Inamdar and Pallavi Jain and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh 2024 Is Part Of LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2024.24 urn:nbn:de:0030-drops-222135 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.24 eng https://creativecommons.org/licenses/by/4.0/legalcode