the complexity and approximability of minimum contamination problems

	the complexity and approximability of minimum contamination problems
	Li Angsheng; Tang Linqing
	2011
会议名称	Theory and Applications of Models of Computation 8th Annual Conference, TAMC 2011
会议录名称	Theory and Applications of Models of Computation
页码	298-307
会议日期	2011
会议地点	Tokyo Japan
出版地	Germany
ISSN	3029743
ISBN	978-3-642-20876-8
部门归属	State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, P.O. Box 8718, Beijing, 100190 P.R. China
摘要	In this article, we investigate the complexity and approximability of the Minimum Contamination Problems, which are derived from epidemic spreading areas and have been extensively studied recently. We show that both the Minimum Average Contamination Problem and the Minimum Worst Contamination Problem are NP-hard problems even on restrict cases. For any ε > 0, we give -bicriteria approximation algorithm for the Minimum Average Contamination Problem. Moreover, we show that the Minimum Average Contamination Problem is NP-hard to be approximated within 5/3 ? ε and the Minimum Worst Contamination Problem is NP-hard to be approximated within 2 ? ε , for any ε > 0, giving the first hardness results of approximation of constant ratios to the problems.
关键词	Approximation Algorithms Computational Complexity Water Cooling Systems
主办者	University of Electro-Communications
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/14215
专题	基础软件与系统重点实验室
推荐引用方式 GB/T 7714	Li Angsheng,Tang Linqing. the complexity and approximability of minimum contamination problems[C]. Germany,2011:298-307.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
the complexity and a（178KB）			开放获取	--	请求全文