Facility Leasing with Penalties

In this paper we study the facility leasing problem with penalties. We present a 3-approximation primal-dual algorithm, based on the algorithms by Nagarajan and Williamson for the facility leasing problem and by Charikar, Khuller, Mount and Narasimhan for the facility location problem with penalties. In the facility location problem, it is given a metric space (V, d), a set F ⊆ V of facilities, an opening cost for each facility, and a set D ⊆ V of clients. The goal is to choose a subset of facilities to open and an assignment between clients and facilities which minimize the cost of opening the facilities plus the sum of the distances from each client to its corresponding facility. This problem does not admit a polynomial-time algorithm with approximation factor smaller than 1.463 unless P = NP [Sviridenko 2002]. Currently the best approximation factor is 1.488 [Li 2013].