Approximating the tau-relaxed soft capacitated facility location problem

doi:10.1007/s10878-020-00631-y

CSpace

	Approximating the tau-relaxed soft capacitated facility location problem
	Han, Lu 1; Xu, Dachuan 2; Xu, Yicheng 3; Zhang, Dongmei 4
	2020-08-01
发表期刊	JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN	1382-6905
页码	13
摘要	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.
关键词	Facility location problem Relaxed triangle inequality Soft capacitated Approximation algorithm Primal-dual
DOI	10.1007/s10878-020-00631-y
收录类别	SCI
语种	英语
资助项目	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类目	Computer Science, Interdisciplinary Applications ; Mathematics, Applied
WOS记录号	WOS:000554448100001
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/51919
专题	中国科学院数学与系统科学研究院
通讯作者	Zhang, Dongmei
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China 2.Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China 3.Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen 518055, Peoples R China 4.Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, 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.