direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

FPT Approximation Schemes for Maximizing Submodular Functions

Piotr Skowron (TU Berlin)


We investigate the existence of approximation algorithms for maximization of submodular functions, that run in a fixed parameter tractable (FPT) time. Given a non-decreasing submodular set function v: 2^X -> 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.


Piotr Skowron
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras