ﻻ يوجد ملخص باللغة العربية
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 $epsilon$-additive approximate minimizer in $tilde{O}(n/epsilon^2)$ oracle evaluations with high probability. This improves over the $tilde{O}(n^{5/3}/epsilon^2)$ oracle evaluation algorithm of Chakrabarty etal~(STOC 2017) and the $tilde{O}(n^{3/2}/epsilon^2)$ oracle evaluation algorithm of Hamoudi etal. 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 $frac{partial^2f}{partial x_i partial x_j} le 0$ for all $i eq j$ and is $L$-Lipschitz with respect to the $L^infty$-norm we give an algorithm that computes an $epsilon$-additive approximate minimizer with $tilde{O}(n cdot mathrm{poly}(L/epsilon))$ function evaluation with high probability.
Submodular function minimization (SFM) is a fundamental discrete optimization problem which generalizes many well known problems, has applications in various fields, and can be solved in polynomial time. Owing to applications in computer vision and m
This paper bridges discrete and continuous optimization approaches for decomposable submodular function minimization, in both the standard and parametric settings. We provide improved running times for this problem by reducing it to a number of cal
In this paper we study the fundamental problems of maximizing a continuous non-monotone submodular function over the hypercube, both with and without coordinate-wise concavity. This family of optimization problems has several applications in machine
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 $argmin_S {f(S)}$ using as few queries to $f(cdot)$ as possible. State-of-the-ar
It has been observed independently by many researchers that the isolating cut lemma of Li and Panigrahi [FOCS 2020] can be easily extended to obtain new algorithms for finding the non-trivial minimizer of a symmetric submodular function and solving t