Metric k-Median

Metric -median is the problem of choosing at most candidate facilities to minimize the sum of distances from clients to their nearest chosen facilities in a metric space. For finite client and candidate sets and , a metric , and a positive integer , the optimum is

For clients 0, 1, and 2 and candidates 0 and 2 with distance , the optimum for is 3.