The one-way communication complexity of submodular maximization with applications to streaming and robustness
The one-way communication complexity of submodular maximization with applications to streaming and robustness
复制标题
DOI：
10.1145/3357713.3384286
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
Moran Feldman;A. Norouzi-Fard;O. Svensson;R. Zenklusen
中科院分区：
文献类型：
--
作者：
Moran Feldman;A. Norouzi-Fard;O. Svensson;R. Zenklusen
我们认为最大化单调下调功能的经典问题受到了基数约束，由于其众多应用，该功能最近在各种计算模型中都研究过。并在单向通信复杂性的方面进行研究我们的模型的单向通信复杂性结果，由于上述连接，在数据流和鲁棒设置中具有多重影响，即使对于两个播放器，就有一个先前的信息理论硬度结果意味着上面没有近似因素如果仅查询可行的集合，即尊重基数约束的集合，我们可以在我们的模型中实现1/2。 2/3-符合指数时间，有效的0.514-轴承。鲁棒的设置，这两种算法都可以改善鲁棒的稳健下管式最大化的最新算法，表明超过1/2的近似因素是可能的。基于新的覆盖函数家族的构造，通过提出紧密的1/2+ε硬度结果来流算法。最著名的近似算法。
We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studied in various computational models. We consider a clean multi-player model that lies between the offline and streaming model, and study it under the aspect of one-way communication complexity. Our model captures the streaming setting (by considering a large number of players), and, in addition, two player approximation results for it translate into the robust setting. We present tight one-way communication complexity results for our model, which, due to the above-mentioned connections, have multiple implications in the data stream and robust setting. Even for just two players, a prior information-theoretic hardness result implies that no approximation factor above 1/2 can be achieved in our model, if only queries to feasible sets, i.e., sets respecting the cardinality constraint, are allowed. We show that the possibility of querying infeasible sets can actually be exploited to beat this bound, by presenting a tight 2/3-approximation taking exponential time, and an efficient 0.514-approximation. To the best of our knowledge, this is the first example where querying a submodular function on infeasible sets leads to provably better results. Through the above-mentioned link to the robust setting, both of these algorithms improve on the current state-of-the-art for robust submodular maximization, showing that approximation factors beyond 1/2 are possible. Moreover, exploiting the link of our model to streaming, we settle the approximability for streaming algorithms by presenting a tight 1/2+ε hardness result, based on the construction of a new family of coverage functions. This improves on a prior 1−1/e+ε hardness and matches, up to an arbitrarily small margin, the best known approximation algorithm.