10.4230/LIPICS.FSTTCS.2009.2321
Huang, Chien-Chung
Chien-Chung
Huang
Svitkina, Zoya
Zoya
Svitkina
Donation Center Location Problem
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2009
Article
Approximation Algorithms
Facility Location
Matching with Preferences
Kannan, Ravi
Ravi
Kannan
Kumar, K. Narayan
K. Narayan
Kumar
2009
2009-12-14
2009-12-14
2009-12-14
en
urn:nbn:de:0030-drops-23212
10.4230/LIPIcs.FSTTCS.2009
978-3-939897-13-2
1868-8969
10.4230/LIPIcs.FSTTCS.2009
LIPIcs, Volume 4, FSTTCS 2009
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
2013
4
20
227
238
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Kannan, Ravi
Ravi
Kannan
Kumar, K. Narayan
K. Narayan
Kumar
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2009
4
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
122628 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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 graph-theoreticproblem.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
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 line-metric.
We present constant-factor approximation algorithms
for the former and exact polynomial-time 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.
LIPIcs, Vol. 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 227-238