University of Leicester
Browse
2.pdf (748.58 kB)

Facility Leasing with Penalties

Download (748.58 kB)
conference contribution
posted on 2020-05-21, 12:23 authored by Murilo 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].

Funding

In author order: ∗Supported by FAPESP/CAPES Proc. 2014/18781-1, and CNPq Proc. 142161/2014-4.†Supported by CAPES PNPD scholarship 1522390.‡Supported by CNPq Proc. 311373/2015-1, and FAPESP Proc. 2015/11937-9

History

Citation

DE LIMA, Murilo Santos; SAN FELICE, Mário César; LEE, Orlando. Facility Leasing with Penalties. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 2. , 2017, São Paulo. Proceedings of the 2nd Theory of Computation Meeting. Porto Alegre: Sociedade Brasileira de Computação, july 2017 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2017.3188.

Source

The 2nd Theory of Computation Meeting (ETC 2017) II Encontro de Teoria da Computação

Version

  • VoR (Version of Record)

Published in

2017: PROCEEDINGS OF THE 2ND THEORY OF COMPUTATION MEETING / 2017: ANAIS DO II ENCONTRO DE TEORIA DA COMPUTAÇÃO

Pagination

27 - 30 (4)

Publisher

Sociedade Brasileira de Computação - SBC

issn

2595-6116

Copyright date

2017

Spatial coverage

São Paulo

Temporal coverage: start date

2017-07-02

Temporal coverage: end date

2017-06-06

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC