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...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , , |
| التنسيق: | conferenceObject |
| منشور في: |
2017
|
| الوصول للمادة أونلاين: | 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 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| الملخص: | 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 |
|---|