Kanellopoulos, Panagiotis and Voudouris, Alexandros and Zhang, Rongsen (2023) On Discrete Truthful Heterogeneous Two-Facility Location. SIAM Journal on Discrete Mathematics, 37 (2). pp. 779-799. DOI https://doi.org/10.1137/22M149908X
Kanellopoulos, Panagiotis and Voudouris, Alexandros and Zhang, Rongsen (2023) On Discrete Truthful Heterogeneous Two-Facility Location. SIAM Journal on Discrete Mathematics, 37 (2). pp. 779-799. DOI https://doi.org/10.1137/22M149908X
Kanellopoulos, Panagiotis and Voudouris, Alexandros and Zhang, Rongsen (2023) On Discrete Truthful Heterogeneous Two-Facility Location. SIAM Journal on Discrete Mathematics, 37 (2). pp. 779-799. DOI https://doi.org/10.1137/22M149908X
Abstract
We revisit the discrete heterogeneous two-facility location problem, in which there is a set of agents that occupy nodes of a line graph and have private approval preferences over two facilities. When the facilities are located at some nodes of the line, each agent suffers a cost that is equal to her total distance from the facilities she approves. The goal is to decide where to locate the two facilities so as to (a) incentivize the agents to truthfully report their preferences and (b) achieve a good approximation of the minimum total (social) cost or the maximum cost among all agents. For both objectives, we design deterministic strategyproof mechanisms with approximation ratios that significantly outperform the state of the art and complement these results with (almost) tight lower bounds.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | facility location; mechanism design; approximation |
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: | 16 Jun 2023 11:37 |
Last Modified: | 07 Aug 2024 17:37 |
URI: | http://repository.essex.ac.uk/id/eprint/34339 |
Available files
Filename: Two_facility_location_on_a_line_path (3).pdf