TY - CONF
T1 - Algorithms for facility location problems with outliers
T2 - Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms
Y1 - 2001
A1 - Charikar,Moses
A1 - Khuller, Samir
A1 - Mount, Dave
A1 - Narasimhan,Giri
AB - 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.
JA - Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms
T3 - SODA '01
PB - Society for Industrial and Applied Mathematics
CY - Philadelphia, PA, USA
SN - 0-89871-490-7
UR - http://dl.acm.org/citation.cfm?id=365411.365555
ER -