  It has been observed in many places that constant-factor approximable
problems often admit polynomial or even linear problem kernels for their
decision versions, e.g., Vertex Cover, Feedback Vertex Set, and Triangle
Packing. While there exist examples like Bin Packing, which does not admit any
kernel unless P = NP, there apparently is a strong relation between these two
polynomial-time techniques. We add to this picture by showing that the natural
decision versions of all problems in two prominent classes of constant-factor
approximable problems, namely MIN F^+\Pi_1 and MAX NP, admit polynomial problem
kernels. Problems in MAX SNP, a subclass of MAX NP, are shown to admit kernels
with a linear base set, e.g., the set of vertices of a graph. This extends
results of Cai and Chen (JCSS 1997), stating that the standard
parameterizations of problems in MAX SNP and MIN F^+\Pi_1 are fixed-parameter
tractable, and complements recent research on problems that do not admit
polynomial kernelizations (Bodlaender et al. JCSS 2009).
