New Query Lower Bounds for Submodular Function MInimization
New Query Lower Bounds for Submodular Function MInimization
复制标题
DOI：
10.4230/lipics.itcs.2020.64
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
A. Graur;Tristan Pollner;Vidhya Ramaswamy;S. Weinberg
中科院分区：
文献类型：
--
作者：
A. Graur;Tristan Pollner;Vidhya Ramaswamy;S. Weinberg
我们考虑在Oracle模型中最小化的子模块函数：给定的Black-box访问subsodular SET函数$ f：2^{[n]} \ rightarrow \ Mathbb {r} $，查找$ \ arg arg \ min_s \ \ {的元素f（s）\} $使用少量查询到$ f（\ cdot）$。最先进的算法以$ \ tilde {o}（n^2）$ QUERIES [LEESW15]成功，但是最著名的下限从未超过$ n $ [HARVEY08]。我们提供了一个$ 2N $的查询下限，用于最小化$ 2n $，$ 3N/2-2 $查询的下限，用于对称的supsodular函数的非平常最小化器，以及$ \ binom {n} {2} {查询不对称下函数的非平凡最小化器的查询下限。我们的$ 3N/2-2 $下界从SFM下限和新颖概念之间的连接下降结果，我们称图的剪切维度。有趣的是，这可以在无方向的加权图中找到$ 3N/2-2 $切割的下限，但我们也证明它不能在$ s $的$ n+1 $上产生优于$ n+1 $的下限 - $ T $ mincut，即使在有指示的加权图中。
We consider submodular function minimization in the oracle model: given black-box access to a submodular set function $f:2^{[n]}\rightarrow \mathbb{R}$, find an element of $\arg\min_S \{f(S)\}$ using as few queries to $f(\cdot)$ as possible. State-of-the-art algorithms succeed with $\tilde{O}(n^2)$ queries [LeeSW15], yet the best-known lower bound has never been improved beyond $n$ [Harvey08]. We provide a query lower bound of $2n$ for submodular function minimization, a $3n/2-2$ query lower bound for the non-trivial minimizer of a symmetric submodular function, and a $\binom{n}{2}$ query lower bound for the non-trivial minimizer of an asymmetric submodular function. Our $3n/2-2$ lower bound results from a connection between SFM lower bounds and a novel concept we term the cut dimension of a graph. Interestingly, this yields a $3n/2-2$ cut-query lower bound for finding the global mincut in an undirected, weighted graph, but we also prove it cannot yield a lower bound better than $n+1$ for $s$-$t$ mincut, even in a directed, weighted graph.