Kanellopoulos, Panagiotis and Voudouris, Alexandros (2026) Constrained Truthful Obnoxious Two-Facility Location with Optional Preferences. Algorithmica, 88 (3). DOI https://doi.org/10.1007/s00453-026-01391-7
Kanellopoulos, Panagiotis and Voudouris, Alexandros (2026) Constrained Truthful Obnoxious Two-Facility Location with Optional Preferences. Algorithmica, 88 (3). DOI https://doi.org/10.1007/s00453-026-01391-7
Kanellopoulos, Panagiotis and Voudouris, Alexandros (2026) Constrained Truthful Obnoxious Two-Facility Location with Optional Preferences. Algorithmica, 88 (3). DOI https://doi.org/10.1007/s00453-026-01391-7
Abstract
We consider a truthful facility location problem with agents that have private positions on the line of real numbers and known optional preferences over two obnoxious facilities that must be placed at locations chosen from a given set of candidate ones. Each agent wants to maximize the sum of distances from the facilities that affect her, and our goal is to design mechanisms that decide where to place the facilities so as to maximize the total happiness of the agents as well as provide the right incentives to them to truthfully report their positions. We consider separately the setting in which all agents are affected by both facilities (i.e., they have non-optional preferences) and the general optional setting. We show tight bounds on the approximation ratio of deterministic strategyproof mechanisms for both settings, and almost tight bounds for randomized mechanisms.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Mechanism design; Obnoxious facility location; Optional preferences; Approximation ratio |
| Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
| SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
| Depositing User: | Unnamed user with email elements@essex.ac.uk |
| Date Deposited: | 09 Jun 2026 15:24 |
| Last Modified: | 09 Jun 2026 15:25 |
| URI: | http://repository.essex.ac.uk/id/eprint/43224 |
Available files
Filename: s00453-026-01391-7.pdf
Licence: Creative Commons: Attribution 4.0