Facility Leasing with Penalties - de Lima, Murilo Santos; San Felice, Mário César; Lee, Orlando (Anais do Encontro de Teoria da Computação (ETC), 2017)
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.