Bo Peng

Breaking the 4-Approximation Barrier in Strategyproof Two-Facility Location

We study strategyproof mechanism design without transfers for the two-facility location problem in metric spaces. A mechanism selects two facility locations based on agents'reported locations; each agent incurs her distance to the nearer facility, and the objective is to minimize the expected social cost. A mechanism i...