Data reductions and combinatorial bounds for improved approximation algorithms
作者：
Highlights：
• We introduce data reduction rules for obtaining approximation algorithms for maximization problems.
• These rules are combined with certain combinatorial insights often typical for kernelization algorithms.
• The resulting algorithms are of a combinatorial nature, yet better than previous published work in at least two special cases.
• We discuss several concrete problems that are natural maximization versions of well-studied domination-type graph problems.
摘要
•We introduce data reduction rules for obtaining approximation algorithms for maximization problems.•These rules are combined with certain combinatorial insights often typical for kernelization algorithms.•The resulting algorithms are of a combinatorial nature, yet better than previous published work in at least two special cases.•We discuss several concrete problems that are natural maximization versions of well-studied domination-type graph problems.
论文关键词：Reduction rules,Maximization problems,Polynomial-time approximation,Domination problems
论文评审过程：Received 14 November 2014, Accepted 2 November 2015, Available online 3 December 2015, Version of Record 29 December 2015.
论文官网地址：https://doi.org/10.1016/j.jcss.2015.11.010
