# On Truthful Constrained Heterogeneous Facility Location with Max-Variant Cost

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Sep 2023.

## Built on by (most cited first, 1 of 1)

- [Compatibility of Max and Sum Objectives for Committee Selection and k-Facility Location](https://mlsanity.com/paper/2507.17063/) (2025)

## Abstract (arXiv)

We consider a problem where agents have private positions on a line, and public approval preferences over two facilities, and their cost is the maximum distance from their approved facilities. The goal is to decide the facility locations to minimize the total and the max cost, while incentivizing the agents to be truthful. We design a strategyproof mechanism that is simultaneously 11- and 5-approximate for these two objective functions, thus improving the previously best-known bounds of 2n+1 and 9.