Polynomial kernels for weighted problems

摘要: We use a technique by Frank and Tardos (Combinatorica 1987) to settle an open problem in kernelization.We present polynomial kernelization for Knapsack parameterized number of items.The method can be generally used obtain kernels weighted problems.We give e.g. Subset Sum, Weighted d-Hitting Set, ILP with bounded variables. Kernelization is formalization efficient preprocessing NP -hard problems using the framework complexity. It has been asked many times whether there are deterministic kernelizations Sum Knapsack. answer both questions affirmatively algorithm compressing numbers due 1987). further illustrate its applicability giving versions several well-studied problems. Furthermore, when different item sizes we exponential Finally, results integer programs.