The complexity and approximability of minimum contamination problems

Angsheng Li; Linqing Tang

doi:10.1007/978-3-642-20877-5_30

The complexity and approximability of minimum contamination problems

Angsheng Li
, Linqing Tang^*

^*Corresponding author for this work

CAS - Institute of Software
University of Chinese Academy of Sciences

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

6 Scopus citations

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 (1 + ε, O(1+ε/ε log n))-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.

Original language	English
Title of host publication	Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings
Publisher	Springer Verlag
Pages	298-307
Number of pages	10
ISBN (Print)	9783642208768
DOIs	https://doi.org/10.1007/978-3-642-20877-5_30
State	Published - 2011
Externally published	Yes
Event	8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011 - Tokyo, Japan Duration: 23 May 2011 → 25 May 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6648 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011
Country/Territory	Japan
City	Tokyo
Period	23/05/11 → 25/05/11

Access to Document

10.1007/978-3-642-20877-5_30

Cite this

Li, A., & Tang, L. (2011). The complexity and approximability of minimum contamination problems. In Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings (pp. 298-307). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6648 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-20877-5_30

Li, Angsheng ; Tang, Linqing. / The complexity and approximability of minimum contamination problems. Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings. Springer Verlag, 2011. pp. 298-307 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0475acd135e4496eb21820371e19abf5,

title = "The complexity and approximability of minimum contamination problems",

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 (1 + ε, O(1+ε/ε log n))-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.",

author = "Angsheng Li and Linqing Tang",

year = "2011",

doi = "10.1007/978-3-642-20877-5\_30",

language = "英语",

isbn = "9783642208768",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "298--307",

booktitle = "Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings",

address = "德国",

note = "8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011 ; Conference date: 23-05-2011 Through 25-05-2011",

}

Li, A & Tang, L 2011, The complexity and approximability of minimum contamination problems. in Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6648 LNCS, Springer Verlag, pp. 298-307, 8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011, Tokyo, Japan, 23/05/11. https://doi.org/10.1007/978-3-642-20877-5_30

The complexity and approximability of minimum contamination problems. / Li, Angsheng; Tang, Linqing.
Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings. Springer Verlag, 2011. p. 298-307 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6648 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - The complexity and approximability of minimum contamination problems

AU - Li, Angsheng

AU - Tang, Linqing

PY - 2011

Y1 - 2011

N2 - 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 (1 + ε, O(1+ε/ε log n))-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.

AB - 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 (1 + ε, O(1+ε/ε log n))-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.

UR - https://www.scopus.com/pages/publications/79955780623

U2 - 10.1007/978-3-642-20877-5_30

DO - 10.1007/978-3-642-20877-5_30

M3 - 会议稿件

AN - SCOPUS:79955780623

SN - 9783642208768

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 298

EP - 307

BT - Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings

PB - Springer Verlag

T2 - 8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011

Y2 - 23 May 2011 through 25 May 2011

ER -

Li A, Tang L. The complexity and approximability of minimum contamination problems. In Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings. Springer Verlag. 2011. p. 298-307. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-20877-5_30

The complexity and approximability of minimum contamination problems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this