Polynomial kernels for weighted problems
作者：
Highlights：
• We use a technique by Frank and Tardos (Combinatorica 1987) to settle an open problem in kernelization.
• We present a polynomial kernelization for Knapsack parameterized by number of items.
• The method can be generally used to obtain polynomial kernels for weighted problems.
• We give kernels for e.g. Subset Sum, Weighted d-Hitting Set, and ILP with bounded variables.
摘要
•We use a technique by Frank and Tardos (Combinatorica 1987) to settle an open problem in kernelization.•We present a polynomial kernelization for Knapsack parameterized by number of items.•The method can be generally used to obtain polynomial kernels for weighted problems.•We give kernels for e.g. Subset Sum, Weighted d-Hitting Set, and ILP with bounded variables.
论文关键词：Kernelization for weighted parameterized problems,FPT,Knapsack,Subset Sum,Integer Linear Programming with bounded variables
论文评审过程：Received 4 January 2016, Accepted 19 June 2016, Available online 26 August 2016, Version of Record 14 November 2016.
论文官网地址：https://doi.org/10.1016/j.jcss.2016.06.004
