---
tag: NPH3AHZN00
kind: concept
name: Metric k-center
aliases: [k-center, minimum-k-center, vertex-k-center-problem]
sources:
  - wikipedia: en:25385291@r1369265357
    locator: Metric k-center
    note: adopted
    mention: wikipedia://en/25385291
    sections: [Summary]
same_as:
  wikidata: Q6824324
  wikipedia: Metric k-center
inventory: [ZRBVA7RSHG]
---

## Summary

In graph theory, the **metric $k$-center** problem or **vertex k-center problem** is a classical combinatorial optimization problem studied in theoretical computer science that is NP-hard. Given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of a city to a warehouse. In graph theory, this means finding a set of $k$ vertices for which the largest distance of any point to its closest vertex in the $k$-set is minimum. The vertices must be in a [[metric space|063W5JMY85]], providing a [[complete graph|03WKB2H474]] that satisfies the [[triangle inequality|03HF5PMY5T]]. It has application in facility location and clustering.