Approximating the tau-relaxed soft capacitated facility location problem
文献类型：期刊论文
| 作者 | Han, Lu2; Xu, Dachuan3; Xu, Yicheng4; Zhang, Dongmei1 |
| 刊名 | JOURNAL OF COMBINATORIAL OPTIMIZATION
 |
| 出版日期 | 2020-08-01 |
| 页码 | 13 |
| 关键词 | Facility location problem Relaxed triangle inequality Soft capacitated Approximation algorithm Primal-dual |
| ISSN号 | 1382-6905 |
| DOI | 10.1007/s10878-020-00631-y |
| 英文摘要 | 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 F, a client set and a parameter tau >= 1. Every facility i is an element of F has a capacity u(i) and an opening cost f(i), and can be opened multiple times. If facility i is opened l times, this facility can be connected by at most lu(i) clients and incurs an opening cost of 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)-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 + epsilon to 10. |
| 资助项目 | Natural Science Foundation of China[11531014] ; Natural Science Foundation of China[11871081] ; Natural Science Foundation of China[11901558] ; China Postdoctoral Science Foundation[2018M643233] |
| WOS研究方向 | Computer Science ; Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000554448100001 |
| 出版者 | SPRINGER |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/51918]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | Zhang, Dongmei |
| 作者单位 | 1.Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China 3.Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China 4.Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen 518055, Peoples R China |
| 推荐引用方式 GB/T 7714 | Han, Lu,Xu, Dachuan,Xu, Yicheng,et al. Approximating the tau-relaxed soft capacitated facility location problem[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION,2020:13. |
| APA | Han, Lu,Xu, Dachuan,Xu, Yicheng,&Zhang, Dongmei.(2020).Approximating the tau-relaxed soft capacitated facility location problem.JOURNAL OF COMBINATORIAL OPTIMIZATION,13. |
| MLA | Han, Lu,et al."Approximating the tau-relaxed soft capacitated facility location problem".JOURNAL OF COMBINATORIAL OPTIMIZATION (2020):13. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。