Facility Leasing with Penalties

  • Murilo Santos de Lima
  • Mário César San Felice
  • Orlando Lee


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].

Como Citar

Selecione um Formato
DE LIMA, Murilo Santos; SAN FELICE, Mário César; LEE, Orlando. Facility Leasing with Penalties. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 2. , 2017, São Paulo. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2017 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2017.3188.