Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2502.09412 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913692204924928 |
|---|---|
| author | Xiao, Hanyin Zhang, Jiaming Zhang, Zhikang Li, Weidong |
| author_facet | Xiao, Hanyin Zhang, Jiaming Zhang, Zhikang Li, Weidong |
| contents | The soft capacitated facility location problem (SCFLP) is a classic combinatorial optimization problem, with its variants widely applied in the fields of operations research and computer science. In the SCFLP, given a set $\mathcal{F}$ of facilities and a set $\mathcal{D}$ of clients, each facility has a capacity and an open cost, allowing to open multiple times, and each client has a demand.
This problem is to find a subset of facilities in $\mathcal{F}$ and connect each client to the facilities opened, such that the total cost including open cost and connection cost is minimied. SCFLP is a NP-hard problem, which has led to a focus on approximation algorithms. Based on this, we consider a variant, that is, soft capacitated facility location problem with submodular penalties (SCFLPSP), which allows some clients not to be served by accepting the penalty cost. And we consider the integer splittable case of demand, that is, the demand of each client is served by multiple facilities with the integer service amount by each facility. Based on LP-rounding, we propose a $(λR+4)$-approximation algorithm, where $R=\frac{\max_{i \in \mathcal{F} }f_i}{\min_{i \in \mathcal{F} }f_i},λ=\frac{R+\sqrt{R^2+8R}}{2R}$. In particular, when the open cost is uniform, the approximation ratio is 6. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_09412 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A LP-rounding based algorithm for soft capacitated facility location problem with submodular penalties Xiao, Hanyin Zhang, Jiaming Zhang, Zhikang Li, Weidong Data Structures and Algorithms Combinatorics The soft capacitated facility location problem (SCFLP) is a classic combinatorial optimization problem, with its variants widely applied in the fields of operations research and computer science. In the SCFLP, given a set $\mathcal{F}$ of facilities and a set $\mathcal{D}$ of clients, each facility has a capacity and an open cost, allowing to open multiple times, and each client has a demand. This problem is to find a subset of facilities in $\mathcal{F}$ and connect each client to the facilities opened, such that the total cost including open cost and connection cost is minimied. SCFLP is a NP-hard problem, which has led to a focus on approximation algorithms. Based on this, we consider a variant, that is, soft capacitated facility location problem with submodular penalties (SCFLPSP), which allows some clients not to be served by accepting the penalty cost. And we consider the integer splittable case of demand, that is, the demand of each client is served by multiple facilities with the integer service amount by each facility. Based on LP-rounding, we propose a $(λR+4)$-approximation algorithm, where $R=\frac{\max_{i \in \mathcal{F} }f_i}{\min_{i \in \mathcal{F} }f_i},λ=\frac{R+\sqrt{R^2+8R}}{2R}$. In particular, when the open cost is uniform, the approximation ratio is 6. |
| title | A LP-rounding based algorithm for soft capacitated facility location problem with submodular penalties |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2502.09412 |