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.