Budgeted Red-Blue Median and Its Generalizations
Budgeted Red-Blue Median and Its Generalizations
复制标题
DOI：
10.1007/978-3-642-15775-2_27
复制
发表时间：
2010-09
期刊：
影响因子：
--
通讯作者：
M. Hajiaghayi;R. Khandekar;G. Kortsarz
中科院分区：
文献类型：
--
作者：
M. Hajiaghayi;R. Khandekar;G. Kortsarz
In a Content Distribution Network application, we have a set of servers and a set of clients to be connected to the servers. Often there are a few server types and a hard budget constraint on the number of deployed servers of each type. The simplest goal here is to deploy a set of servers subject to these budget constraints in order to minimize the sum of client connection costs. These connection costs often satisfy metricity, since they are typically proportional to the distance between a client and a server within a single autonomous system. A special case of the problem where there is only one server type is the well-studiedk-medianproblem.In this paper, we consider the problem with two server types and call it thebudgeted red-blue medianproblem. We show, somewhat surprisingly, that running a single-swap local search for each server typesimultaneously, yields a constant factor approximation for this case. Its analysis is however quite non-trivial compared to that of thek-median problem (Arya et al., 2004; Gupta and Tangwongsan, 2008).Later we show that the same algorithm yields a constant approximation for theprize-collectingversion of the budgeted red-blue median problem where each client can potentially be served with an alternative cost via a different vendor. In the process, we also improve the approximation factor for theprize-collecting k-medianproblem from 4 (Charikar et al., 2001) to 3 +ε, which matches the current best approximation factor for thek-median problem.
