License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2321
URN: urn:nbn:de:0030-drops-23212
URL: http://drops.dagstuhl.de/opus/volltexte/2009/2321/
Go to the corresponding Portal


Huang, Chien-Chung ; Svitkina, Zoya

Donation Center Location Problem

pdf-format:
Document 1.pdf (120 KB)


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 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.

BibTeX - Entry

@InProceedings{huang_et_al:LIPIcs:2009:2321,
  author =	{Chien-Chung Huang and Zoya Svitkina},
  title =	{{Donation Center Location Problem}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{227--238},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Ravi Kannan and K. Narayan Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2321},
  URN =		{urn:nbn:de:0030-drops-23212},
  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


DROPS-Home | Fulltext Search | Imprint Published by LZI