Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142626 | Operations Research Letters | 2011 | 4 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Moritz A. Drexl,