LP rounding for k-centers with non-uniform hard capacities

Marek Cygan*, Mohammadtaghi Hajiaghayi, Samir Khuller

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

38 Scopus citations

Abstract

In this paper we consider a generalization of the classical k-center problem with capacities. Our goal is to select k centers in a graph, and assign each node to a nearby center, so that we respect the capacity constraints on centers. The objective is to minimize the maximum distance a node has to travel to get to its assigned center. This problem is NP-hard, even when centers have no capacity restrictions and optimal factor 2 approximation algorithms are known. With capacities, when all centers have identical capacities, a 6 approximation is known with no better lower bounds than for the infinite capacity version. While many generalizations and variations of this problem have been studied extensively, no progress was made on the capacitated version for a general capacity function. We develop the first constant factor approximation algorithm for this problem. Our algorithm uses an LP rounding approach to solve this problem, and works for the case of non-uniform hard capacities, when multiple copies of a node may not be chosen and can be extended to the case when there is a hard bound on the number of copies of a node that may be selected. Finally, for non-uniform soft capacities we present a much simpler 11-approximation algorithm, which we find as one more evidence that hard capacities are much harder to deal with.

Original languageEnglish (US)
Article number6375305
Pages (from-to)273-282
Number of pages10
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs
StatePublished - 2012
Event53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012 - New Brunswick, NJ, United States
Duration: Oct 20 2012Oct 23 2012

Keywords

  • LP rounding
  • approximation algorithms
  • hard capacities
  • k-center
  • non-uniform capacities

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'LP rounding for k-centers with non-uniform hard capacities'. Together they form a unique fingerprint.

Cite this