Abstract
We introduce and study the {\em donation center location} problem, which
has an additional application in network
testing and may also be of independent interest as a general graphtheoreticproblem.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 maximumsized subset of agents to their mostpreferred
open centers, while respecting the capacity constraints.
We prove that in general, the problem
is hard to approximate within $n^{1/2\epsilon}$ for any $\epsilon>0$.
In view of this, we investigate two special cases.
In one, every agent has a bounded number of centers on her preference list,
and in the other, all preferences are induced by a linemetric.
We present constantfactor approximation algorithms
for the former and exact polynomialtime algorithms for the latter.
Of particular interest among our techniques are an analysis of the greedy
algorithm for a variant of the maximum coverage problem called\emph{frugal coverage}, the use of maximum matching subroutine with subsequent
modification, analyzed using a counting argument, and a reduction to the independent set problem
on \emph{terminal intersection graphs}, which we show to be
a subclass of trapezoid graphs.
BibTeX  Entry
@InProceedings{huang_et_al:LIPIcs:2009:2321,
author = {ChienChung Huang and Zoya Svitkina},
title = {{Donation Center Location Problem}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {227238},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897132},
ISSN = {18688969},
year = {2009},
volume = {4},
editor = {Ravi Kannan and K. Narayan Kumar},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2321},
URN = {urn:nbn:de:0030drops23212},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2009.2321},
annote = {Keywords: Approximation Algorithms, Facility Location, Matching with Preferences}
}
Keywords: 

Approximation Algorithms, Facility Location, Matching with Preferences 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science 
Issue Date: 

2009 
Date of publication: 

14.12.2009 