Invitation to data reduction and problem kernelization

343 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Infeasibility of instance compression and succinct PCPs for NP (2007, neutral): “In their survey on kernelization, Guo and Niedermeier [14] state, “In terms of computational complexity theory, the derivation of lower bounds is of the utmost importance.”
(Meta) Kernelization (2009, methodology): “The first step towards the general abstraction of all these algorithms was initiated by Guo and Niedermeier [38], who introduced the notion of “problems with distance property”.”
Handbook of Computational Social Choice (2016, background): “Even when the existence of polynomial-time algorithms for a certain problem is unlikely, we may still hope for polynomial-time data reduction rules that provably reduce the size of the input instance (Guo and Niedermeier, 2007).”
On problems without polynomial kernels (2009, methodology): “In this sense, kernelization can be viewed as polynomial-time preprocessing which has universal applicability, not only in the design of efficient FPT algorithms, but also in the design of approximation and heuristic algorithms [40].”
Design and Analysis of Algorithms (2009, methodology): “For online randomized caching with uniform costs and page sizes, [13] presented the log 2k-competitive marking algorithm and [14] gave a log k-competitive algorithm, which is the best possible competitive ratio.”