K-Center problems with minimum coverage

Andrew Lim, Brian Rodrigues, Fan Wang, Zhou Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

157 Citations (Scopus)


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
Issue number1-3
Publication statusPublished - 28 Feb 2005
Externally publishedYes


  • Approximation algorithm
  • k-center problem
  • Minimum coverage

ASJC Scopus subject areas

  • Computational Theory and Mathematics


Dive into the research topics of 'K-Center problems with minimum coverage'. Together they form a unique fingerprint.

Cite this