A Two-Stage Constrained Submodular Maximization
A Two-Stage Constrained Submodular Maximization
复制标题
两阶段约束子模最大化
DOI：
10.1007/978-3-030-27195-4_30
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Ruiqi Yang, Shuyang Gu
中科院分区：
文献类型：
--
作者：
Ruiqi Yang, Shuyang Gu
我们考虑了p-拟阵(ORP-Extendible)约束下的两阶段子模极大化问题。在该模型中，给出了一个子模函数集合和每个函数的拟阵(或可扩展)系统约束，我们需要选择一个具有基数约束的代表集，同时选择一系列限制到所有函数的代表集的子集，目标是最大化这些函数值的总和的平均值。我们将单拟阵下的两阶段子模极大化推广到句柄拟阵(ORP-eXtendible)约束，并分别推导了这两个问题的恒定逼近比算法。最后，我们在一些数据集上实证证明了该方法的有效性。
We consider a two-stage submodular maximization underp-matroid (orp-extendible) constraints. In the model, we are given a collection of submodular functions and somep-matroid (or extendible) system constraints for each of these functions, one need to choose a representative set with a cardinality constraint and simultaneously select a series of subsets that are restricted to the representative set for all functions, the aim is to maximize the average of the summarization of these function values. We extend the two-stage submodular maximization under single matroid to handlep-matroid (orp-extendible) constraints, and derive constant approximation ratio algorithms for the two problems, respectively. In the end, we empirically demonstrate the efficiency of our method on some datasets.
DOI：
10.1287/moor.1100.0463
发表时间：
2009-08
期刊：
Math. Oper. Res.
影响因子：
--
作者：
Jon Lee;M. Sviridenko;J. Vondrák
通讯作者：
Jon Lee;M. Sviridenko;J. Vondrák