×

Approximation algorithms for the squared metric \(k\)-level facility location problem. (Chinese. English summary) Zbl 1374.90275

Summary: In this paper, we study the squared metric \(k\)-level facility location problem where the facilities are on \(k\)-level. The objective is to minimize the sum of the opening cost and the connection cost. Using the LP-rounding techniques, we then propose an approximation algorithm and obtain the approximation ratio of \(9\). Furthermore, we study the squared metric \(k\)-level soft capacitied facility location problem. Using the LP-rounding techniques, we then propose an approximation algorithm and obtain the approximation ratio of \(12.2216\).

MSC:

90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
90C05 Linear programming
PDFBibTeX XMLCite