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 | |
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 | Korea, Republic of |
City | Jeonju |
Period | 15/12/14 → 17/12/14 |