On Truthful Constrained Facility Location with Max-Variant Cost
share
We consider a problem where agents are positioned on a line, have 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 show that a simple strategyproof mechanism is 7-approximate for the total cost and 5-approximate for the max cost, thus improving upon the previous bounds of 2n+1 and 9.
READ FULL TEXT