An approximation algorithm for the kk-Level Concentrator Location Problem

The kk-Level Concentrator Location Problem is a variant of the kk-Level Facility Location Problem, where in contrast to the classical model, service costs are charged only once and not proportional to the demand. We present a new approximation algorithm with a performance guarantee of 32(3k−1), improving over the 1.52⋅9k−11.52⋅9k−1-approximation algorithm proposed by Kantor and Peleg. Moreover, the analysis is considerably shortened by using complementary slackness conditions.

► We analyze the kk-Level Concentrator Location Problem.
► An approximation algorithm is presented with ratio 3k3k.
► Complementary Slackness is used to prove the result.