Submodular maximization with matroid and packing constraints in parallel
Submodular maximization with matroid and packing constraints in parallel
复制标题
并行拟阵和填充约束的子模最大化
DOI：
10.1145/3313276.3316389
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Vladu, Adrian
中科院分区：
文献类型：
--
作者：
Ene, Alina;Nguyen, Huy L.;Vladu, Adrian
我们考虑了在单个拟阵约束或多个打包约束下，通过少量自适应轮次评估查询来最大化子模函数的多线性扩展的问题。我们获得了第一个具有拟阵约束的子模最大化低自适应性的算法。我们的算法实现了单调函数的 1−1/e−є 近似和非单调函数的 1/e−є 近似，这几乎与完全自适应设置中已知的最佳保证相匹配。自适应轮数为O(log2n/є3)，比现有算法有指数加速。我们得到了第一个受包装约束的非单调子模最大化并行算法。我们的算法使用 O(log(n/є) log(1/є) log(n+m)/ є2) 轮并行实现了 1/e−є 近似，这又比现有算法在并行时间上实现了指数加速。对于单调函数，我们在 O(log(n/є)logm/є2) 轮并行中获得 1−1/e−є 近似值。我们算法的并行轮数与用线性目标求解打包 LP 的最先进算法相匹配（Mahoney 等人，2016）。我们的结果更普遍地适用于最大化收益递减子模（DR-子模）函数的问题。
We consider the problem of maximizing the multilinear extension of a submodular function subject a single matroid constraint or multiple packing constraints with a small number of adaptive rounds of evaluation queries.We obtain the first algorithms with low adaptivity for submodular maximization with a matroid constraint. Our algorithms achieve a 1−1/e−є approximation for monotone functions and a 1/e−є approximation for non-monotone functions, which nearly matches the best guarantees known in the fully adaptive setting. The number of rounds of adaptivity isO(log2n/є3), which is an exponential speedup over the existing algorithms.We obtain the first parallel algorithm for non-monotone submodular maximization subject to packing constraints. Our algorithm achieves a 1/e−є approximation usingO(log(n/є) log(1/є) log(n+m)/ є2) parallel rounds, which is again an exponential speedup in parallel time over the existing algorithms. For monotone functions, we obtain a 1−1/e−є approximation inO(log(n/є)logm/є2) parallel rounds. The number of parallel rounds of our algorithm matches that of the state of the art algorithm for solving packing LPs with a linear objective (Mahoney et al., 2016).Our results apply more generally to the problem of maximizing a diminishing returns submodular (DR-submodular) function.
登录
查看更多内容
DOI：
10.1137/1.9781611975482.19
发表时间：
2018-04
期刊：
--
影响因子：
--
作者：
Eric Balkanski;A. Rubinstein;Yaron Singer
通讯作者：
Eric Balkanski;A. Rubinstein;Yaron Singer
DOI：
--
发表时间：
2018-07
期刊：
ArXiv
影响因子：
--
作者：
Eric Balkanski;Adam Breuer;Yaron Singer
通讯作者：
Eric Balkanski;Adam Breuer;Yaron Singer
DOI：
10.1006/jcom.1994.1025
发表时间：
1994
期刊：
J. Complex.
影响因子：
--
作者：
A. Nemirovski
通讯作者：
A. Nemirovski
DOI：
--
发表时间：
2015-02
期刊：
ArXiv
影响因子：
--
作者：
R. Barbosa;Alina Ene;Huy L. Nguyen;Justin Ward
通讯作者：
R. Barbosa;Alina Ene;Huy L. Nguyen;Justin Ward
具有最佳逼近、适应性和查询复杂性的子模最大化
DOI：
--
发表时间：
2018
期刊：
arXiv.org
影响因子：
--
作者：
Matthew Fahrbach;V. Mirrokni;Morteza Zadimoghaddam
通讯作者：
Morteza Zadimoghaddam