Donation Center Location Problem

We introduce and study the donation center location problem, which has an additional application in network testing and may also be of independent interest as a general graph-theoretic problem. Given a set of agents and a set of centers, where agents have preferences over centers and centers have capacities, the goal is to open a subset of centers and to assign a maximum-sized subset of agents to their most-preferred opened centers, while respecting the capacity constraints. We prove that in general, the problem is hard to approximate within n ^1/2?? for any ?>0. In view of this, we investigate two special cases. In one, every agent has a bounded number of centers on its preference list, and in the other, all preferences are induced by a line-metric. We present constant-factor approximation algorithms for the former and exact polynomial-time algorithms for the latter.