## Matthias Bentert, René van Bevern, Till Fluschnik, André Nichterlein, and
Rolf Niedermeier.
Polynomial-time preprocessing for weighted problems beyond additive
goal functions.
2019.

Kernelization is the fundamental notion for
polynomial-time prepocessing with performance
guarantees in parameterized algorithmics. When
preprocessing weighted problems, the need of
shrinking weights might arise. Marx and Végh [ACM
Trans. Algorithms 2015] and Etscheid et
al. [J. Comput. Syst. Sci. 2017] used a technique
due to Frank and Tardos [Combinatorica 1987] that we
refer to as losing-weight technique to obtain
kernels of polynomial size for weighted
problems. While the mentioned earlier works focus on
problems with additive goal functions, we focus on a
broader class of goal functions. We lift the
losing-weight technique to what we call linearizable
goal functions, which also contain non-additive
functions. We apply the lifted technique to five
exemplary problems, thereby improving two results
from the literature by proving polynomial kernels.

[ bib |
http ]
Back

*This file was generated by
bibtex2html 1.99.*