论文标题
改进的下限以最小化的下函数
Improved Lower Bounds for Submodular Function Minimization
论文作者
论文摘要
我们提供了一种通用技术，用于构建子模函数的家族，以获得下界功能最小化（SFM）的下限。应用此技术，我们证明了$ n $元素的地面集的任何确定性SFM算法都需要至少$ω（n \ log n）$ QUERIES $ QUERIES对评估Oracle。这是SFM的第一个超级线性查询复杂性下限，并且在[Graur等人，ITCS 2020]给出的先前最佳下限$ 2N $中改善。使用我们的构造，我们还证明了任何（可能是随机的）并行SFM算法，这些算法最多可以弥补$ \ Mathsf {poly}（n）$ queries $ queries $ queries每回合，都需要至少$ω（n / \ log n）$ rounds，以最大程度地减少子函数。由于[Chakrabarty等人，focs 2021]，$ \tildeΩ（n^{1/3}）$ roughs的先前最佳下限进行了改善，并解决了由于最近在[Jiang，Soda，Soda 20211]中，由于最近在[Jiang，Soda，Soda 2021]中，查询效率SFM的并行复杂性达到了对数因素的平行复杂性。
We provide a generic technique for constructing families of submodular functions to obtain lower bounds for submodular function minimization (SFM). Applying this technique, we prove that any deterministic SFM algorithm on a ground set of $n$ elements requires at least $Ω(n \log n)$ queries to an evaluation oracle. This is the first super-linear query complexity lower bound for SFM and improves upon the previous best lower bound of $2n$ given by [Graur et al., ITCS 2020]. Using our construction, we also prove that any (possibly randomized) parallel SFM algorithm, which can make up to $\mathsf{poly}(n)$ queries per round, requires at least $Ω(n / \log n)$ rounds to minimize a submodular function. This improves upon the previous best lower bound of $\tildeΩ(n^{1/3})$ rounds due to [Chakrabarty et al., FOCS 2021], and settles the parallel complexity of query-efficient SFM up to logarithmic factors due to a recent advance in [Jiang, SODA 2021].
