Capacitated Center Problems with Two-Sided Bounds and Outliers
Capacitated Center Problems with Two-Sided Bounds and Outliers
复制标题
DOI：
10.1007/978-3-319-62127-2_28
复制
发表时间：
2017-02
期刊：
影响因子：
--
通讯作者：
Hu Ding;Lunjia Hu;Lingxiao Huang;J. Li
中科院分区：
文献类型：
--
作者：
Hu Ding;Lunjia Hu;Lingxiao Huang;J. Li
近年来，容量限制中心问题引起了人们的广泛研究兴趣。给定一组顶点V，我们希望找到顶点S的子集，称为中心，使得最大聚类半径最小化。此外，S中的每个中心应该满足一些容量约束，该容量约束可以是它可以服务的顶点数量的上限或下限。具有单侧界（上界或下界）的容量k-中心问题在以前的工作中得到了很好的研究，并得到了一个常数因子逼近，本文首次研究了具有容量下界和容量上界（有或无野值）的容量约束中心问题.我们假设每个顶点有一个一致的下界和一个非一致的上界。对于开放exactlykcenters的情况下，我们注意到，最近的LP方法的推广可以实现常数因子近似算法为我们的问题。我们的主要贡献是针对开放中心数量没有基数约束的情况提出了一种简单的组合算法。我们的组合算法是简单的，实现更好的常数逼近因子相比，LP方法。
In recent years, the capacitated center problems have attracted a lot of research interest. Given a set of verticesV, we want to find a subset of verticesS, called centers, such that the maximum cluster radius is minimized. Moreover, each center inSshould satisfy some capacity constraint, which could be an upper or lower bound on the number of vertices it can serve. Capacitatedk-center problems with one-sided bounds (upper or lower) have been well studied in previous work, and a constant factor approximation was obtained.We are the first to study the capacitated center problem with both capacity lower and upper bounds (with or without outliers). We assume each vertex has a uniform lower bound and a non-uniform upper bound. For the case of opening exactlykcenters, we note that a generalization of a recent LP approach can achieve constant factor approximation algorithms for our problems. Our main contribution is a simple combinatorial algorithm for the case where there is no cardinality constraint on the number of open centers. Our combinatorial algorithm is simpler and achieves better constant approximation factor compared to the LP approach.