A survey of techniques, this paper presents and analyzes algorithms and constructs fixed parameter tractable approximation schemes. These schemes are “collections of algorithms that run in [fixed parameter tractable, FPT] time and can achieve arbitrarily good approximation ratios.” The FPT problem can be solved by a fixed parameter algorithm. This core combinatorial optimization technique builds on the “polynomial relation between the computation time and the size of an instance,” for example, “for each fixed k the problem is soluble in time bounded by a polynomial of degree c, where c is a constant independent of k” [1].

The “maximization of non-decreasing submodular functions” has applications in a variety of research areas. The purpose of the proposed research is to prove “the existence of FPT approximation schemes” for use cases in computational social choice, matching theory, and theoretical computer science. FPT approximation can create minimization or maximization variants of a problem of interest for specific parameters, and run algorithms in FPT time for these parameters.

The paper provides several parameters that are considered “suitable for the analysis of the complexity of the maximization of non-decreasing submodular functions,” for example, the size of solutions or a property of set functions (p-separability). The reviewed algorithms cover two variants of the problem: maximization variant and minimization variant. They have the same optimal solutions, but “they are not equivalent in terms of their approximability.”

Each algorithm is described, discussed, and presented with proofs and examples in a very thorough manner, followed by an explanation of its applications (item selection in multiagent systems, matching and assignment problems, and the MaxWeightCover problem).

A well-written and well-argued paper, with adequate positioning within the related work, it is very good reading for scholars and students interested in algorithms, approximation, and submodular functions.