论文标题
suplipular最大化的单向通信复杂性，以及用于流和鲁棒性的应用
The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
论文作者
论文摘要
我们考虑了受基数限制的最大化单调性函数最大化的经典问题，由于其众多应用，该功能最近在各种计算模型中进行了研究。我们考虑了一个干净的多人模型，该模型位于离线模型和流式模型之间，并在单向通信复杂性方面进行研究。我们的模型捕获了流设置（通过考虑大量玩家），此外，两个播放器近似结果将转化为健壮的设置。我们为模型提供了紧密的单向通信复杂性结果，由于上述连接，在数据流和健壮设置中具有多重影响。 即使对于两个玩家，先前的信息理论硬度结果也意味着，如果仅允许对可行集合的疑问，则在我们的模型中无法实现高于$ 1/2 $的近似因素。我们表明，实际上可以利用查询不可行的套件来击败这种界限，这是通过提出$ 2/3 $ - approximation花费指数时间和有效的$ 0.514 $ approximation来击败这种界限的可能性。据我们所知，这是第一个示例，在不可行的集合上查询superodular函数会导致结果更好的结果。通过上述链接与健壮设置，这两种算法都可以改善当前最新的稳健少量最大化，这表明近似因子超过$ 1/2 $。此外，利用我们的模型与流媒体的链接，我们根据建立了新的覆盖范围功能系列，通过呈现紧密的$ 1/2+\ varepsilon $硬度结果来解决流媒体算法的近似性。这在先前的$ 1-1/e+\ varepsilon $硬度和匹配项上提高了，最多是最小的边距，是最著名的近似算法。
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 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+\varepsilon$ hardness result, based on the construction of a new family of coverage functions. This improves on a prior $1-1/e+\varepsilon$ hardness and matches, up to an arbitrarily small margin, the best known approximation algorithm.
