K-Center problems with minimum coverage

Andrew Lim, Brian Rodrigues, Fan Wang, Zhou Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

138 Citations (Scopus)

Abstract

In this work, we study an extension of the k-center facility location problem, where centers are required to service a minimum of clients. This problem is motivated by requirements to balance the workload of centers while allowing each center to cater to a spread of clients. We study three variants of this problem, all of which are shown to be NP-hard. In-approximation hardness and approximation algorithms with factors equal or close to the best lower bounds are provided. Generalizations, including vertex costs and vertex weights, are also studied.
Original languageEnglish
Pages (from-to)1-17
Number of pages17
JournalTheoretical Computer Science
Volume332
Issue number1-3
DOIs
Publication statusPublished - 28 Feb 2005
Externally publishedYes

Keywords

  • Approximation algorithm
  • k-center problem
  • Minimum coverage

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Cite this