FPT approximation schemes for maximizing submodular functions
FPT approximation schemes for maximizing submodular functions
复制标题
DOI：
10.1016/j.ic.2017.10.002
复制
发表时间：
2015-10
期刊：
影响因子：
--
通讯作者：
P. Skowron
中科院分区：
文献类型：
--
作者：
P. Skowron
我们调查存在的近似算法最大化的次模函数，运行在一个固定的参数易处理（FPT）的时间。给定一个非减次模集函数v：2 X→ R，目标是从X中选择一个K个元素的子集S，使得v（S）最大化。我们确定了三个属性的集函数，称为p-可分性的属性，我们认为，许多现实生活中的问题可以表示为最大化的子模块，p-可分离的功能，与低的参数p值。我们提出FPT近似方案的最小化和最大化的问题的变体，几个参数取决于优化的集函数的特性，如p和K。
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.