# Compatibility of Max and Sum Objectives for Committee Selection and k-Facility Location

arXiv: https://arxiv.org/abs/2507.17063 · HTML: https://mlsanity.com/paper/2507.17063/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 30 references that are in the map.
- First posted on arXiv 22 Jul 2025.

## Builds on (most cited first, 12 of 12)

- [Distortion in Social Choice Problems: The First 15 Years and Beyond](https://mlsanity.com/paper/2103.00911/) (2021)
- [Mechanism Design for Facility Location Problems: A Survey](https://mlsanity.com/paper/2106.03457/) (2021)
- [Resolving the Optimal Metric Distortion Conjecture](https://mlsanity.com/paper/2004.07447/) (2020)
- [The Metric Distortion of Multiwinner Voting](https://mlsanity.com/paper/2201.13332/) (2022)
- [Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median](https://mlsanity.com/paper/1711.08715/) (2017)
- [Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion](https://mlsanity.com/paper/2206.07098/) (2022)
- [Strategy Proof Mechanisms for Facility Location at Limited Locations](https://mlsanity.com/paper/2009.07982/) (2020)
- [Optimizing Multiple Simultaneous Objectives for Voting and Facility Location](https://mlsanity.com/paper/2212.03467/) (2022)
- [Facility Location Games with Ordinal Preferences](https://mlsanity.com/paper/2107.01649/) (2021)
- [Truthful Two-Facility Location with Candidate Locations](https://mlsanity.com/paper/2305.07525/) (2023)
- [On Truthful Constrained Heterogeneous Facility Location with Max-Variant Cost](https://mlsanity.com/paper/2309.05379/) (2023)
- [Agent-Constrained Truthful Facility Location Games](https://mlsanity.com/paper/2405.05197/) (2024)

## Abstract (arXiv)

We study a version of the metric facility location problem (or, equivalently, variants of the committee selection problem) in which we must choose k facilities in an arbitrary metric space to serve some set of clients C. We consider four different objectives, where each client i∈ C attempts to minimize either the sum or the maximum of its distance to the chosen facilities, and where the overall objective either considers the sum or the maximum of the individual client costs. Rather than optimizing a single objective at a time, we study how compatible these objectives are with each other, and show the existence of solutions which are simultaneously close-to-optimum for any pair of the above objectives. Our results show that when choosing a set of facilities or a representative committee, it is often possible to form a solution which is good for several objectives at the same time, instead of sacrificing one desideratum to achieve another.