Polynomial kernels for weighted problems

Michael Etscheid; Stefan Kratsch; Matthias Mnich; Heiko Röglin

doi:10.1016/j.jcss.2016.06.004

Polynomial kernels for weighted problems

Michael Etscheid^*, Stefan Kratsch, Matthias Mnich, Heiko Röglin

^*Corresponding author for this work

QE Operations research

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

Kernelization is a formalization of efficient preprocessing for NP-hard problems using the framework of parameterized complexity. It has been asked many times whether there are deterministic polynomial kernelizations for SUBSET SUM and KNAPSACK. We answer both questions affirmatively by using an algorithm for compressing numbers due to Frank and Tardos (Combinatorica 1987). We further illustrate its applicability by giving polynomial kernels for weighted versions of several well-studied parameterized problems. Furthermore, when parameterized by the different item sizes we obtain a polynomial kernelization for SUBSET SUM and an exponential kernelization for KNAPSACK. Finally, we obtain kernelization results for polynomial integer programs. (C) 2016 Elsevier Inc. All rights reserved.

Original language	English
Pages (from-to)	1-10
Number of pages	10
Journal	Journal of Computer and System Sciences
Volume	84
DOIs	https://doi.org/10.1016/j.jcss.2016.06.004
Publication status	Published - Mar 2017

Keywords

Kernelization for weighted parameterized problems
FPT
Knapsack
Subset Sum
Integer Linear Programming with bounded variables
APPROXIMATION
FIXED NUMBER

Access to Document

10.1016/j.jcss.2016.06.004

Cite this

@article{7fc3c1518a074ede9f783f540a96acac,

title = "Polynomial kernels for weighted problems",

abstract = "Kernelization is a formalization of efficient preprocessing for NP-hard problems using the framework of parameterized complexity. It has been asked many times whether there are deterministic polynomial kernelizations for SUBSET SUM and KNAPSACK. We answer both questions affirmatively by using an algorithm for compressing numbers due to Frank and Tardos (Combinatorica 1987). We further illustrate its applicability by giving polynomial kernels for weighted versions of several well-studied parameterized problems. Furthermore, when parameterized by the different item sizes we obtain a polynomial kernelization for SUBSET SUM and an exponential kernelization for KNAPSACK. Finally, we obtain kernelization results for polynomial integer programs. (C) 2016 Elsevier Inc. All rights reserved.",

keywords = "Kernelization for weighted parameterized problems, FPT, Knapsack, Subset Sum, Integer Linear Programming with bounded variables, APPROXIMATION, FIXED NUMBER",

author = "Michael Etscheid and Stefan Kratsch and Matthias Mnich and Heiko R{\"o}glin",

note = "No data used.",

year = "2017",

month = mar,

doi = "10.1016/j.jcss.2016.06.004",

language = "English",

volume = "84",

pages = "1--10",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Polynomial kernels for weighted problems

AU - Etscheid, Michael

AU - Kratsch, Stefan

AU - Mnich, Matthias

AU - Röglin, Heiko

N1 - No data used.

PY - 2017/3

Y1 - 2017/3

N2 - Kernelization is a formalization of efficient preprocessing for NP-hard problems using the framework of parameterized complexity. It has been asked many times whether there are deterministic polynomial kernelizations for SUBSET SUM and KNAPSACK. We answer both questions affirmatively by using an algorithm for compressing numbers due to Frank and Tardos (Combinatorica 1987). We further illustrate its applicability by giving polynomial kernels for weighted versions of several well-studied parameterized problems. Furthermore, when parameterized by the different item sizes we obtain a polynomial kernelization for SUBSET SUM and an exponential kernelization for KNAPSACK. Finally, we obtain kernelization results for polynomial integer programs. (C) 2016 Elsevier Inc. All rights reserved.

AB - Kernelization is a formalization of efficient preprocessing for NP-hard problems using the framework of parameterized complexity. It has been asked many times whether there are deterministic polynomial kernelizations for SUBSET SUM and KNAPSACK. We answer both questions affirmatively by using an algorithm for compressing numbers due to Frank and Tardos (Combinatorica 1987). We further illustrate its applicability by giving polynomial kernels for weighted versions of several well-studied parameterized problems. Furthermore, when parameterized by the different item sizes we obtain a polynomial kernelization for SUBSET SUM and an exponential kernelization for KNAPSACK. Finally, we obtain kernelization results for polynomial integer programs. (C) 2016 Elsevier Inc. All rights reserved.

KW - Kernelization for weighted parameterized problems

KW - FPT

KW - Knapsack

KW - Subset Sum

KW - Integer Linear Programming with bounded variables

KW - APPROXIMATION

KW - FIXED NUMBER

U2 - 10.1016/j.jcss.2016.06.004

DO - 10.1016/j.jcss.2016.06.004

M3 - Article

SN - 0022-0000

VL - 84

SP - 1

EP - 10

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

ER -