Approximating the $$\tau $$ τ -relaxed soft capacitated facility location problem

Lu Han (), Dachuan Xu (), Yicheng Xu () and Dongmei Zhang ()
Additional contact information
Lu Han: Chinese Academy of Sciences
Dachuan Xu: Beijing University of Technology
Yicheng Xu: Chinese Academy of Sciences
Dongmei Zhang: Shandong Jianzhu University

Journal of Combinatorial Optimization, 2020, vol. 40, issue 3, No 14, 848-860

Abstract: Abstract In this paper, we consider the $$\tau $$ τ -relaxed soft capacitated facility location problem ( $$\tau $$ τ -relaxed SCFLP), which extends several well-known facility location problems like the squared metric soft capacitated facility location problem (SMSCFLP), soft capacitated facility location problem (SCFLP), squared metric facility location problem and uncapacitated facility location problem. In the $$\tau $$ τ -relaxed SCFLP, we are given a facility set $$\mathcal {F}$$ F , a client set and a parameter $$\tau \ge 1$$ τ ≥ 1 . Every facility $$i \in \mathcal {F}$$ i ∈ F has a capacity $$u_i$$ u i and an opening cost $$f_i$$ f i , and can be opened multiple times. If facility i is opened l times, this facility can be connected by at most $$l u_i$$ l u i clients and incurs an opening cost of $$l f_i$$ l f i . Every facility-client pair has a connection cost. Under the assumption that the connection costs are non-negative, symmetric and satisfy the $$\tau $$ τ -relaxed triangle inequality, we wish to open some facilities (once or multiple times) and connect every client to an opened facility without violating the capacity constraint so as to minimize the total opening costs as well as connection costs. As our main contribution, we propose a primal-dual based $$(3 \tau + 1)$$ ( 3 τ + 1 ) -approximation algorithm for the $$\tau $$ τ -relaxed SCFLP. Furthermore, our algorithm not only extends the applicability of the primal-dual technique but also improves the previous approximation guarantee for the SMSCFLP from $$11.18+ \varepsilon $$ 11.18 + ε to 10.

Keywords: Facility location problem; Relaxed triangle inequality; Soft capacitated; Approximation algorithm; Primal-dual (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00631-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:40:y:2020:i:3:d:10.1007_s10878-020-00631-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00631-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().