| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
28 March 2024 |
|
| | | |
|
Article overview
| |
|
Data Reductions and Combinatorial Bounds for Improved Approximation Algorithms | Faisal N. Abu-Khzam
; Cristina Bazgan
; Morgan Chopin
; Henning Fernau
; | Date: |
12 Sep 2014 | 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 extsc{Harmless Set}, extsc{Differential} and
extsc{Multiple Nonblocker}, all of them can be considered in the context of
securing networks or information propagation. | Source: | arXiv, 1409.3742 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |