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

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

0.00 Avg rating0 Votes
Article ID: iaor20171793
Volume: 11
Issue: 5
Start Page Number: 983
End Page Number: 993
Publication Date: Jun 2017
Journal: Optimization Letters
Authors: , , ,
Keywords: combinatorial optimization, facilities
Abstract:

We consider the nth power metric facility location problem with linear penalties (MnFLPLP) in this work, extending both the nth power metric facility location problem (MnFLP) and the metric facility location problem with linear penalties (MFLPLP). We present an LP‐rounding based approximation algorithm to the MnFLPLP with bi‐factor approximation ratio ( γ f , γ c ) equ1 , where γ f equ2 and γ c equ3 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 ( γ f , 1 + ( 3 n 1 ) e γ f ) equ4 when the facility factor γ f > 2 equ5 for the M2FLPLP.

Reviews

Required fields are marked *. Your email address will not be published.