Algorithms for facility location problems with outliers
Algorithms for facility location problems with outliers
复制标题
DOI：
--
复制
发表时间：
2001-01
期刊：
影响因子：
--
通讯作者：
M. Charikar;S. Khuller;D. Mount;G. Narasimhan
中科院分区：
文献类型：
--
作者：
M. Charikar;S. Khuller;D. Mount;G. Narasimhan
设施选址问题是传统的研究假设，所有的客户提供服务。这个公式的一个显著缺点是，一些非常遥远的客户端，称为离群值，可以对最终解决方案施加不成比例的强大影响。在本文中，我们探讨了各种设施选址问题（K-中心，K-中位数，无容量限制的设施位置等）的情况下，只有一个指定的分数的客户提供服务的推广。使问题更难的是，我们还必须选择应该得到服务的子集。我们提供了各种近似算法来处理这个附加的约束。
Facility location problems are traditionally investigated with the assumption that all the clients are to be provided service. A significant shortcoming of this formulation is that a few very distant clients, called outliers, can exert a disproportionately strong influence over the final solution. In this paper we explore a generalization of various facility location problems (K-center, K-median, uncapacitated facility location etc) to the case when only a specified fraction of the customers are to be served. What makes the problems harder is that we have to also select the subset that should get service. We provide generalizations of various approximation algorithms to deal with this added constraint.