Institutional Repository
| the complexity and approximability of minimum contamination problems | |
| Li Angsheng; Tang Linqing | |
| 2011 | |
| Conference Name | Theory and Applications of Models of Computation 8th Annual Conference, TAMC 2011 |
| Source | Theory and Applications of Models of Computation |
| Pages | 298-307 |
| Conference Date | 2011 |
| Conference Place | Tokyo Japan |
| Publish Place | Germany |
| ISSN | 3029743 |
| ISBN | 978-3-642-20876-8 |
| Department | State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, P.O. Box 8718, Beijing, 100190 P.R. China |
| English Abstract | 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. |
| Keyword | Approximation Algorithms Computational Complexity Water Cooling Systems |
| Sponsorship | University of Electro-Communications |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/14215 |
| Collection | 基础软件与系统重点实验室 |
| Recommended Citation GB/T 7714 | Li Angsheng,Tang Linqing. the complexity and approximability of minimum contamination problems[C]. Germany,2011:298-307. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| the complexity and a（178KB） | 开放获取 | -- | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment