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.
