The Fault-Tolerant Facility Location Problem with Submodular Penalties - Collections

＜preprint＞
The Fault-Tolerant Facility Location Problem with Submodular Penalties

Creator	Author PID K004444 Creator Name Kamiyama, Naoyuki 神山, 直之カミヤマ, ナオユキ Affiliation Affiliation Name Institute of Mathematics for Industry, Kyushu University 九州大学マス・フォア・インダストリ研究所
Language	English
Publisher	Faculty of Mathematics, Kyushu University
Publisher	九州大学大学院数理学研究院
Date	2013-12-08
Source Title	MI Preprint Series
Vol	2013-15
Publication Type	Author's Original
Access Rights	open access
Related DOI	MI Preprint Series \|\| 2013-15 \|\| p1-15
Related DOI	http://www.math.kyushu-u.ac.jp/
Related URI	MI Preprint Series \|\| 2013-15 \|\| p1-15
Related URI	http://www.math.kyushu-u.ac.jp/
Relation	MI Preprint Series \|\| 2013-15 \|\| p1-15
Relation	http://www.math.kyushu-u.ac.jp/
Abstract	In this paper, we consider the fault-tolerant facility location problem with submodular penal- ties that is a common generalization of the fault-tolerant facility location problem and the facility loc...ation problem with submodular penalties. For this problem, we present a combinatorial 3 • HR -approximation algorithm, where R is the maximum connectivity requirement and HR is the R-th harmonic number. Our algorithm is a common generalization of the algorithm for the the fault-tolerant facility location problem presented by Jain and Vazirani (2003) and that for the facility location problem with submodular penalties presented by Du, Lu and Xu (2012).show more

File	FileType	Size	Views	Description
MI2013-15	pdf	144 KB	325

Record ID	1398518
Peer-Reviewed	Unrefereed
Notes	Global COE Program Education-and-Research Hub for Mathematics-for-Industry
	グローバルCOEプログラム「マス･フォア･インダストリ教育研究拠点」
	This work is partly supported by KAKENHI(24106005).
	論文の一部は科研費による(24106005)
Type	プレプリント
Type	Preprint
Created Date	2014.02.06
Modified Date	2020.09.30