Polynomial kernels for weighted problems
详细信息 查看全文
- 作者：Michael Etscheid ; etscheid@cs.uni-bonn.de" class="auth_mail" title="E-mail the corresponding author ; Stefan Kratsch kratsch@cs.uni-bonn.de" class="auth_mail" title="E-mail the corresponding author ; Matthias Mnich mmnich@uni-bonn.de" class="auth_mail" title="E-mail the corresponding author ; Heiko Rö ; glin roeglin@cs.uni-bonn.de" class="auth_mail" title="E-mail the corresponding author
- 关键词：Kernelization for weighted parameterized problems ; FPT ; Knapsack ; Subset Sum ; Integer Linear Programming with bounded variables
- 刊名：Journal of Computer and System Sciences
- 出版年：2017
- 出版时间：March 2017
- 年：2017
- 卷：84
- 期：Complete
- 页码：1-10
- 全文大小：352 K
文摘
- •
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.