2026-07-22T13:39:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2321 2024-03-06T10:33:17Z ddc:004 open_access

Donation Center Location Problem Huang, Chien-Chung Svitkina, Zoya Approximation Algorithms Facility Location Matching with Preferences 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chien-Chung Huang and Zoya Svitkina 2009 Is Part Of LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2009.2321 urn:nbn:de:0030-drops-23212 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2321 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode