Approximation algorithms inspired by kernelization nethods

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Bazgan, Cristina
dc.contributor.author Chopin, Morgan
dc.contributor.author Fernau, Henning
dc.date.accessioned 2017-03-17T12:49:17Z
dc.date.available 2017-03-17T12:49:17Z
dc.identifier.uri http://hdl.handle.net/10725/5380
dc.description.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 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 en_US
dc.language.iso en en_US
dc.publisher Springer en_US
dc.title Approximation algorithms inspired by kernelization nethods en_US
dc.type Conference Paper / Proceeding en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.identifier.doi http://dx.doi.org/10.1007/978-3-319-13075-0 38 en_US
dc.identifier.ctation 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. en_US
dc.author.email faisal.abukhzam@lau.edu.lb en_US
dc.conference.date December 15–17, 2014 en_US
dc.conference.pages 479-490 en_US
dc.conference.place Jeonju, Korea en_US
dc.conference.title 25th International Symposium en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php en_US
dc.identifier.url 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 en_US
dc.orcid.id https://orcid.org/0000-0001-5221-8421
dc.author.affiliation Lebanese American University en_US
dc.title.volume Algorithms and Computation en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account