Approximation algorithms inspired by Kernelization methods

Faisal Abu Khzam; Cristina Bazgan; Morgan Chopin; Henning Fernau

doi:10.1007/978-3-319-13075-0_38

Approximation algorithms inspired by Kernelization methods

Faisal Abu Khzam, Cristina Bazgan, Morgan Chopin, Henning Fernau

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

1 Downloads (Pure)

Abstract

Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of reduction rules and combinatorial insights. We will expose in this paper a similar strategy for obtaining polynomial-time approximation algorithms. Our method features the use of approximation-preserving reductions, akin to the notionof parameterized reductions. We exemplify this method to obtain the currently best approximation algorithms for Harmless Set, Differential and Multiple Nonblocker, all of them can be considered in the context of securing networks or information propagation.

Original language	English
Title of host publication	Algorithms and Computation, 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, Lecture Notes in Computer Science Vol 8889
Editors	HK Ahn, CS Shin
Place of Publication	Switzerland
Publisher	Springer
Pages	479-490
Number of pages	12
Edition	1
ISBN (Print)	978-3-319-13074-3
DOIs	https://doi.org/10.1007/978-3-319-13075-0_38
Publication status	Published - 2014
Externally published	Yes
Event	International Symposium on Algorithms and Computation (ISAAC 2014 25th) - Jeonju, Korea, Jeonju, Korea, Republic of Duration: 15 Dec 2014 → 17 Dec 2014 Conference number: 2014 (25th)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	8889
ISSN (Print)	0302-9743

Conference

Conference	International Symposium on Algorithms and Computation (ISAAC 2014 25th)
Abbreviated title	ISAAC
Country/Territory	Korea, Republic of
City	Jeonju
Period	15/12/14 → 17/12/14

Access to Document

10.1007/978-3-319-13075-0_38

Cite this

Abu Khzam, F., Bazgan, C., Chopin, M., & Fernau, H. (2014). Approximation algorithms inspired by Kernelization methods. In HK. Ahn, & CS. Shin (Eds.), Algorithms and Computation, 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, Lecture Notes in Computer Science Vol 8889 (1 ed., pp. 479-490). (Lecture Notes in Computer Science; Vol. 8889). Springer. https://doi.org/10.1007/978-3-319-13075-0_38

Abu Khzam, Faisal ; Bazgan, Cristina ; Chopin, Morgan et al. / Approximation algorithms inspired by Kernelization methods. Algorithms and Computation, 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, Lecture Notes in Computer Science Vol 8889. editor / HK Ahn ; CS Shin. 1. ed. Switzerland : Springer, 2014. pp. 479-490 (Lecture Notes in Computer Science).

@inproceedings{77d88391826340109c079a4fc157e033,

title = "Approximation algorithms inspired by Kernelization methods",

abstract = "Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of reduction rules and combinatorial insights. We will expose in this paper a similar strategy for obtaining polynomial-time approximation algorithms. Our method features the use of approximation-preserving reductions, akin to the notionof parameterized reductions. We exemplify this method to obtain the currently best approximation algorithms for Harmless Set, Differential and Multiple Nonblocker, all of them can be considered in the context of securing networks or information propagation.",

author = "{Abu Khzam}, Faisal and Cristina Bazgan and Morgan Chopin and Henning Fernau",

year = "2014",

doi = "10.1007/978-3-319-13075-0_38",

language = "English",

isbn = "978-3-319-13074-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "479--490",

editor = "HK Ahn and CS Shin",

booktitle = "Algorithms and Computation, 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, Lecture Notes in Computer Science Vol 8889",

address = "Switzerland",

edition = "1",

note = "International Symposium on Algorithms and Computation (ISAAC 2014 25th), ISAAC ; Conference date: 15-12-2014 Through 17-12-2014",

}

Abu Khzam, F, Bazgan, C, Chopin, M & Fernau, H 2014, Approximation algorithms inspired by Kernelization methods. in HK Ahn & CS Shin (eds), Algorithms and Computation, 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, Lecture Notes in Computer Science Vol 8889. 1 edn, Lecture Notes in Computer Science, vol. 8889, Springer, Switzerland, pp. 479-490, International Symposium on Algorithms and Computation (ISAAC 2014 25th), Jeonju, Korea, Republic of, 15/12/14. https://doi.org/10.1007/978-3-319-13075-0_38

Approximation algorithms inspired by Kernelization methods. / Abu Khzam, Faisal; Bazgan, Cristina; Chopin, Morgan et al.

Algorithms and Computation, 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, Lecture Notes in Computer Science Vol 8889. ed. / HK Ahn; CS Shin. 1. ed. Switzerland : Springer, 2014. p. 479-490 (Lecture Notes in Computer Science; Vol. 8889).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

TY - GEN

T1 - Approximation algorithms inspired by Kernelization methods

AU - Abu Khzam, Faisal

AU - Bazgan, Cristina

AU - Chopin, Morgan

AU - Fernau, Henning

N1 - Conference code: 2014 (25th)

PY - 2014

Y1 - 2014

N2 - Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of reduction rules and combinatorial insights. We will expose in this paper a similar strategy for obtaining polynomial-time approximation algorithms. Our method features the use of approximation-preserving reductions, akin to the notionof parameterized reductions. We exemplify this method to obtain the currently best approximation algorithms for Harmless Set, Differential and Multiple Nonblocker, all of them can be considered in the context of securing networks or information propagation.

AB - Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of reduction rules and combinatorial insights. We will expose in this paper a similar strategy for obtaining polynomial-time approximation algorithms. Our method features the use of approximation-preserving reductions, akin to the notionof parameterized reductions. We exemplify this method to obtain the currently best approximation algorithms for Harmless Set, Differential and Multiple Nonblocker, all of them can be considered in the context of securing networks or information propagation.

UR - http://www.springer.com/us/book/9783319130743

U2 - 10.1007/978-3-319-13075-0_38

DO - 10.1007/978-3-319-13075-0_38

M3 - Conference Paper published in Proceedings

SN - 978-3-319-13074-3

T3 - Lecture Notes in Computer Science

SP - 479

EP - 490

BT - Algorithms and Computation, 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, Lecture Notes in Computer Science Vol 8889

A2 - Ahn, HK

A2 - Shin, CS

PB - Springer

CY - Switzerland

T2 - International Symposium on Algorithms and Computation (ISAAC 2014 25th)

Y2 - 15 December 2014 through 17 December 2014

ER -

Abu Khzam F, Bazgan C, Chopin M, Fernau H. Approximation algorithms inspired by Kernelization methods. In Ahn HK, Shin CS, editors, Algorithms and Computation, 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, Lecture Notes in Computer Science Vol 8889. 1 ed. Switzerland: Springer. 2014. p. 479-490. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-13075-0_38

Approximation algorithms inspired by Kernelization methods

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this