Polynomial-Time Data Reduction for Weighted Problems Beyond Additive Goal Functions
From MaRDI portal
Publication:6326311
DOI10.1016/J.DAM.2022.11.018arXiv1910.00277MaRDI QIDQ6326311FDOQ6326311
Authors: Matthias Bentert, René van Bevern, Till Fluschnik, André Nichterlein, Rolf Niedermeier 
Publication date: 1 October 2019
Abstract: Dealing with NP-hard problems, kernelization is a fundamental notion for polynomial-time data reduction with performance guarantees: in polynomial time, a problem instance is reduced to an equivalent instance with size upper-bounded by a function of a parameter chosen in advance. Kernelization for weighted problems particularly requires to also shrink weights. Marx and V'egh [ACM Trans. Algorithms 2015] and Etscheid et al. [J. Comput. Syst. Sci. 2017] used a technique of Frank and Tardos [Combinatorica 1987] to obtain polynomial-size kernels for weighted problems, mostly with additive goal functions. We characterize the function types that the technique is applicable to, which turns out to contain many non-additive functions. Using this insight, we systematically obtain kernelization results for natural problems in graph partitioning, network design, facility location, scheduling, vehicle routing, and computational social choice, thereby improving and generalizing results from the literature.
Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60) Transportation, logistics and supply chain management (90B06)
This page was built for publication: Polynomial-Time Data Reduction for Weighted Problems Beyond Additive Goal Functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6326311)
