Algorithms for facility location problems with outliers

Moses Charikar*, Samir Khuller, David M. Mount, Gin Narasimhan

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

227 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages642-651
Number of pages10
StatePublished - Dec 1 2001
Event2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States
Duration: Apr 30 2001May 1 2001

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other2001 Operating Section Proceedings, American Gas Association
CountryUnited States
CityDallas, TX
Period4/30/015/1/01

Keywords

  • Algorithms
  • Measurement
  • Performance
  • Theory
  • Verification

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Algorithms for facility location problems with outliers'. Together they form a unique fingerprint.

Cite this