The Non-Uniform k-Center Problem
summary
Classic k‑center stays 2‑approx, and the nonuniform version gets concrete results: an LP-to-firefighter reduction converts a fractional solution on the metric to a layered tree and yields a 2‑approx for outliers and a (1+√5)‑type constant for two radii, but if the number of radius types is part of the input there is no unicriterion approximation and the LP shows a log-star n integrality gap so the best provable guarantee becomes an order-one bi-criteria algorithm that opens extra centers of each type.
AI-written summary · about