An approximation algorithm for the nth power metric facility location problem with linear penalties

We consider the nth power metric facility location problem with linear penalties (MⁿFLPLP) in this work, extending both the nth power metric facility location problem (MⁿFLP) and the metric facility location problem with linear penalties (MFLPLP). We present an LP‐rounding based approximation algorithm to the MⁿFLPLP with bi‐factor approximation ratio $({\mathit{\gamma }}_f,{\mathit{\gamma }}_c)$ , where ${\mathit{\gamma }}_f$ and ${\mathit{\gamma }}_c$ are the ratios corresponding to facility, and connection and penalty costs respectively. Finally we show that the bi‐factor curve is close to the lower bound $({\mathit{\gamma }}_f,1+(3^n‐1)e^{‐{\mathit{\gamma }}_f})$ when the facility factor ${\mathit{\gamma }}_f>2$ for the M²FLPLP.