New algorithm achieves optimal 4/3 approximation for two-facility location

A new paper by Panagiotis Kanellopoulos and Alexandros A. Voudouris tackles the discrete heterogeneous two-facility location problem, a classic challenge in algorithmic mechanism design. The problem involves placing two different facilities (e.g., a school and a library) at distinct nodes of a graph while ensuring agents report their preferences truthfully. Each agent incurs a cost equal to the total distance from the facilities they approve. The goal is a deterministic strategyproof mechanism that minimizes social cost — the sum of all agents' costs. For the line graph, previous best-known approximation ratios lay between 4/3 and 17/4. The authors close this gap by constructing an optimal 4/3-approximate mechanism, combining a fixed-parity median rule (for n ≥ 7) with strategyproof local overrides for smaller instances.

Beyond the line, the authors extend their results to arbitrary connected graphs. They design a deterministic strategyproof 2-approximate mechanism that works for any graph topology, along with proving a lower bound of 3/2 on the graph K₁,₃ (a star with three leaves). This establishes that no deterministic strategyproof mechanism can achieve a better approximation than 3/2 on that graph. The work has implications for resource allocation problems where truthfulness is critical, such as public facility placement, network design, and algorithmic pricing.