Near-optimal approximate discrete and continuous submodular function minimization
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2020•SIAM
In this paper we provide improved running times and oracle complexities for approximately
minimizing a submodular function. Our main result is a randomized algorithm, which given
any submodular function defined on n-elements with range [–1, 1], computes an ε-additive
approximate minimizer in Õ (n/ε 2) oracle evaluations with high probability. This improves
over the Õ (n 5/3/ε 2) oracle evaluation algorithm of Chakrabarty et al.(STOC 2017) and the
Õ (n 3/2/ε 2) oracle evaluation algorithm of Hamoudi et al… Further, we leverage a …
minimizing a submodular function. Our main result is a randomized algorithm, which given
any submodular function defined on n-elements with range [–1, 1], computes an ε-additive
approximate minimizer in Õ (n/ε 2) oracle evaluations with high probability. This improves
over the Õ (n 5/3/ε 2) oracle evaluation algorithm of Chakrabarty et al.(STOC 2017) and the
Õ (n 3/2/ε 2) oracle evaluation algorithm of Hamoudi et al… Further, we leverage a …
In this paper we provide improved running times and oracle complexities for approximately minimizing a submodular function. Our main result is a randomized algorithm, which given any submodular function defined on n-elements with range [–1, 1], computes an ε-additive approximate minimizer in Õ(n/ε2) oracle evaluations with high probability. This improves over the Õ(n5/3/ε2) oracle evaluation algorithm of Chakrabarty et al. (STOC 2017) and the Õ(n3/2/ε2) oracle evaluation algorithm of Hamoudi et al…
Further, we leverage a generalization of this result to obtain efficient algorithms for minimizing a broad class of nonconvex functions. For any function f with domain [0, 1]n that satisfies for all i ≠ j and is L-Lipschitz with respect to the L∞-norm we give an algorithm that computes an ε-additive approximate minimizer with Õ(n · poly(L/ε) function evaluation with high probability.
Society for Industrial and Applied Mathematics以上显示的是最相近的搜索结果。 查看全部搜索结果