FPT Approximation Schemes for Maximizing Submodular Functions

Abstract

We investigate the existence of approximation algorithms for maximization of submodular functions, that run in fixed parameter tractable (FPT) time. Given a non-decreasing submodular set function $v:2^X\to \mathbb{R}$ the goal is to select a subset $S$ of $K$ elements from $X$ such that $v(S)$ is maximized. We identify three properties of set functions, referred to as $p$-separability properties, and we argue that many real-life problems can be expressed as maximization of submodular, $p$-separable functions, with low values of the parameter $p$. We present FPT approximation schemes for the minimization and maximization variants of the problem, for several parameters that depend on characteristics of the optimized set function, such as $p$ and $K$. We confirm that our algorithms are applicable to a broad class of problems, in particular to problems from computational social choice, such as item selection or winner determination under several multiwinner election systems.

References in corpus (4)

• Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
• Non-monotone submodular maximization under matroid and knapsack constraints
• Reflection methods for user-friendly submodular optimization
• Structured sparsity-inducing norms through submodular functions