Data reductions and combinatorial bounds for improved approximation algorithms
Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of data 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 approximatio...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | article |
| Published: |
2016
|
| Online Access: | http://hdl.handle.net/10725/4759 http://dx.doi.org/10.1016/j.jcss.2015.11.010 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://www.sciencedirect.com/science/article/pii/S0022000015001336 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513464561565696 |
|---|---|
| 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 | 2016-11-08T13:59:07Z 2016-11-08T13:59:07Z 2016 2016-11-08 |
| dc.identifier.none.fl_str_mv | 0022-0000 http://hdl.handle.net/10725/4759 http://dx.doi.org/10.1016/j.jcss.2015.11.010 Abu-Khzam, F. N., Bazgan, C., Chopin, M., & Fernau, H. (2016). Data reductions and combinatorial bounds for improved approximation algorithms. Journal of Computer and System Sciences, 82(3), 503-520. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://www.sciencedirect.com/science/article/pii/S0022000015001336 |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | Journal of Computer and System Sciences |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | Data reductions and combinatorial bounds for improved approximation algorithms |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of data 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 | article |
| id | LAURepo_5962fcbb41495ecd1707b46012aa8367 |
| identifier_str_mv | 0022-0000 Abu-Khzam, F. N., Bazgan, C., Chopin, M., & Fernau, H. (2016). Data reductions and combinatorial bounds for improved approximation algorithms. Journal of Computer and System Sciences, 82(3), 503-520. |
| 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/4759 |
| publishDate | 2016 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Data reductions and combinatorial bounds for improved approximation algorithmsAbu-Khzam, Faisal N.Bazgan, CristinaChopin, MorganFernau, HenningKernelization algorithms in the context of Parameterized Complexity are often based on a combination of data 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.PublishedN/A2016-11-08T13:59:07Z2016-11-08T13:59:07Z20162016-11-08Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/article0022-0000http://hdl.handle.net/10725/4759http://dx.doi.org/10.1016/j.jcss.2015.11.010Abu-Khzam, F. N., Bazgan, C., Chopin, M., & Fernau, H. (2016). Data reductions and combinatorial bounds for improved approximation algorithms. Journal of Computer and System Sciences, 82(3), 503-520.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttp://www.sciencedirect.com/science/article/pii/S0022000015001336enJournal of Computer and System Sciencesinfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/47592021-03-19T10:00:50Z |
| spellingShingle | Data reductions and combinatorial bounds for improved approximation algorithms Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | Data reductions and combinatorial bounds for improved approximation algorithms |
| title_full | Data reductions and combinatorial bounds for improved approximation algorithms |
| title_fullStr | Data reductions and combinatorial bounds for improved approximation algorithms |
| title_full_unstemmed | Data reductions and combinatorial bounds for improved approximation algorithms |
| title_short | Data reductions and combinatorial bounds for improved approximation algorithms |
| title_sort | Data reductions and combinatorial bounds for improved approximation algorithms |
| url | http://hdl.handle.net/10725/4759 http://dx.doi.org/10.1016/j.jcss.2015.11.010 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://www.sciencedirect.com/science/article/pii/S0022000015001336 |