Key points are not available for this paper at this time.
We consider a truthful two-facility location problem in which there is set of agents with private locations on the line of real numbers, and the goal is to place two facilities at different locations chosen from the set of those reported by the agents. Given a feasible solution, each agent suffers an individual cost which is either its total distance to both facilities (sum-variant) or its distance to the farthest facility (max-variant). For both variants, we show tight bounds on the approximation ratio of deterministic and randomized mechanisms in terms of the social cost, the total individual cost of the agents.
Building similarity graph...
Analyzing shared references across papers
Loading...
Deligkas et al. (Wed,) studied this question.
www.synapsesocial.com/papers/68e6b14fb6db6435876333a5 — DOI: https://doi.org/10.48550/arxiv.2405.05197
Argyrios Deligkas
Mohammad Lotfi
Alexandros A. Voudouris
Building similarity graph...
Analyzing shared references across papers
Loading...