Approximation algorithms inspired by kernelization nethods
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-pre...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | conferenceObject |
| Published: |
2017
|
| Online Access: | http://hdl.handle.net/10725/5380 http://dx.doi.org/10.1007/978-3-319-13075-0 38 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://download.springer.com/static/pdf/606/bok%253A978-3-319-13075-0.pdf?originUrl=http%3A%2F%2Flink.springer.com%2Fbook%2F10.1007%2F978-3-319-13075-0&token2=exp=1489755151~acl=%2Fstatic%2Fpdf%2F606%2Fbok%25253A978-3-319-13075-0.pdf%3ForiginUrl%3Dhttp%253A%252F%252Flink.springer.com%252Fbook%252F10.1007%252F978-3-319-13075-0*~hmac=30221a1c1d93b0118facf97f0ee988f3e7c7a1ccca24556d5cc9b82b58cb3815#page=481 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513465861799936 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Bazgan, Cristina Chopin, Morgan Fernau, Henning |
| author2_role | author author author |
| author_facet | Abu-Khzam, Faisal N. Bazgan, Cristina Chopin, Morgan Fernau, Henning |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Bazgan, Cristina Chopin, Morgan Fernau, Henning |
| dc.date.none.fl_str_mv | 2017-03-17T12:49:17Z 2017-03-17T12:49:17Z 2017-03-17 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/5380 http://dx.doi.org/10.1007/978-3-319-13075-0 38 Chopin, M., & Fernau, H. (2014, November). Approximation algorithms inspired by kernelization methods. In Algorithms and Computation: 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings (Vol. 8889, p. 479). Springer. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://download.springer.com/static/pdf/606/bok%253A978-3-319-13075-0.pdf?originUrl=http%3A%2F%2Flink.springer.com%2Fbook%2F10.1007%2F978-3-319-13075-0&token2=exp=1489755151~acl=%2Fstatic%2Fpdf%2F606%2Fbok%25253A978-3-319-13075-0.pdf%3ForiginUrl%3Dhttp%253A%252F%252Flink.springer.com%252Fbook%252F10.1007%252F978-3-319-13075-0*~hmac=30221a1c1d93b0118facf97f0ee988f3e7c7a1ccca24556d5cc9b82b58cb3815#page=481 |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | Springer |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | Approximation algorithms inspired by kernelization nethods Algorithms and Computation |
| dc.type.none.fl_str_mv | Conference Paper / Proceeding info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/conferenceObject |
| description | 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 notion of 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 |
| eu_rights_str_mv | openAccess |
| format | conferenceObject |
| id | LAURepo_90bf1fd7686f6a5d8ad0252930e4a693 |
| identifier_str_mv | Chopin, M., & Fernau, H. (2014, November). Approximation algorithms inspired by kernelization methods. In Algorithms and Computation: 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings (Vol. 8889, p. 479). Springer. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/5380 |
| publishDate | 2017 |
| publisher.none.fl_str_mv | Springer |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Approximation algorithms inspired by kernelization nethodsAlgorithms and ComputationAbu-Khzam, Faisal N.Bazgan, CristinaChopin, MorganFernau, HenningKernelization 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 notion of 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 propagationN/ASpringer2017-03-17T12:49:17Z2017-03-17T12:49:17Z2017-03-17Conference Paper / Proceedinginfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/conferenceObjecthttp://hdl.handle.net/10725/5380http://dx.doi.org/10.1007/978-3-319-13075-0 38Chopin, M., & Fernau, H. (2014, November). Approximation algorithms inspired by kernelization methods. In Algorithms and Computation: 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings (Vol. 8889, p. 479). Springer.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttp://download.springer.com/static/pdf/606/bok%253A978-3-319-13075-0.pdf?originUrl=http%3A%2F%2Flink.springer.com%2Fbook%2F10.1007%2F978-3-319-13075-0&token2=exp=1489755151~acl=%2Fstatic%2Fpdf%2F606%2Fbok%25253A978-3-319-13075-0.pdf%3ForiginUrl%3Dhttp%253A%252F%252Flink.springer.com%252Fbook%252F10.1007%252F978-3-319-13075-0*~hmac=30221a1c1d93b0118facf97f0ee988f3e7c7a1ccca24556d5cc9b82b58cb3815#page=481eninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/53802021-03-19T10:03:22Z |
| spellingShingle | Approximation algorithms inspired by kernelization nethods Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | Approximation algorithms inspired by kernelization nethods |
| title_full | Approximation algorithms inspired by kernelization nethods |
| title_fullStr | Approximation algorithms inspired by kernelization nethods |
| title_full_unstemmed | Approximation algorithms inspired by kernelization nethods |
| title_short | Approximation algorithms inspired by kernelization nethods |
| title_sort | Approximation algorithms inspired by kernelization nethods |
| url | http://hdl.handle.net/10725/5380 http://dx.doi.org/10.1007/978-3-319-13075-0 38 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://download.springer.com/static/pdf/606/bok%253A978-3-319-13075-0.pdf?originUrl=http%3A%2F%2Flink.springer.com%2Fbook%2F10.1007%2F978-3-319-13075-0&token2=exp=1489755151~acl=%2Fstatic%2Fpdf%2F606%2Fbok%25253A978-3-319-13075-0.pdf%3ForiginUrl%3Dhttp%253A%252F%252Flink.springer.com%252Fbook%252F10.1007%252F978-3-319-13075-0*~hmac=30221a1c1d93b0118facf97f0ee988f3e7c7a1ccca24556d5cc9b82b58cb3815#page=481 |