Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
103
0
0.0
(
0
)
Added by
Georgios Amanatidis
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Constrained submodular maximization problems encompass a wide variety of applications, including personalized recommendation, team formation, and revenue maximization via viral marketing. The massive instances occurring in modern day applications can render existing algorithms prohibitively slow, while frequently, those instances are also inherently stochastic. Focusing on these challenges, we revisit the classic problem of maximizing a (possibly non-monotone) submodular function subject to a knapsack constraint. We present a simple randomized greedy algorithm that achieves a $5.83$ approximation and runs in $O(n log n)$ time, i.e., at least a factor $n$ faster than other state-of-the-art algorithms. The robustness of our approach allows us to further transfer it to a stochastic version of the problem. There, we obtain a $9$-approximation to the best adaptive policy, which is the first constant approximation for non-monotone objectives. Experimental evaluation of our algorithms showcases their improved performance on real and synthetic data.
rate research
Read More
The growing need to deal with massive instances motivates the design of algorithms balancing the quality of the solution with applicability. For the latter, an important measure is the emph{adaptive complexity}, capturing the number of sequential rounds of parallel computation needed. In this work we obtain the first emph{constant factor} approximation algorithm for non-monotone submodular maximization subject to a knapsack constraint with emph{near-optimal} $O(log n)$ adaptive complexity. Low adaptivity by itself, however, is not enough: one needs to account for the total number of function evaluations (or value queries) as well. Our algorithm asks $tilde{O}(n^2)$ value queries, but can be modified to run with only $tilde{O}(n)$ instead, while retaining a low adaptive complexity of $O(log^2n)$. Besides the above improvement in adaptivity, this is also the first emph{combinatorial} approach with sublinear adaptive complexity for the problem and yields algorithms comparable to the state-of-the-art even for the special cases of cardinality constraints or monotone objectives. Finally, we showcase our algorithms applicability on real-world datasets.
We study the problem of maximizing a monotone $k$-submodular function $f$ under a knapsack constraint, where a $k$-submodular function is a natural generalization of a submodular function to $k$ dimensions. We present a deterministic $(frac12-frac{1}{2e})$-approximation algorithm that evaluates $f$ $O(n^5k^4)$ times.
In this work, we give a new parallel algorithm for the problem of maximizing a non-monotone diminishing returns submodular function subject to a cardinality constraint. For any desired accuracy $epsilon$, our algorithm achieves a $1/e - epsilon$ approximation using $O(log{n} log(1/epsilon) / epsilon^3)$ parallel rounds of function evaluations. The approximation guarantee nearly matches the best approximation guarantee known for the problem in the sequential setting and the number of parallel rounds is nearly-optimal for any constant $epsilon$. Previous algorithms achieve worse approximation guarantees using $Omega(log^2{n})$ parallel rounds. Our experimental evaluation suggests that our algorithm obtains solutions whose objective value nearly matches the value obtained by the state of the art sequential algorithms, and it outperforms previous parallel algorithms in number of parallel rounds, iterations, and solution quality.
As the scales of data sets expand rapidly in some application scenarios, increasing efforts have been made to develop fast submodular maximization algorithms. This paper presents a currently the most efficient algorithm for maximizing general non-negative submodular objective functions subject to $k$-extendible system constraints. Combining the sampling process and the decreasing threshold strategy, our algorithm Sample Decreasing Threshold Greedy Algorithm (SDTGA) obtains an expected approximation guarantee of ($p-epsilon$) for monotone submodular functions and of ($p(1-p)-epsilon$) for non-monotone cases with expected computational complexity of only $O(frac{pn}{epsilon}lnfrac{r}{epsilon})$, where $r$ is the largest size of the feasible solutions, $0<p leq frac{1}{1+k}$ is the sampling probability and $0< epsilon < p$. If we fix the sampling probability $p$ as $frac{1}{1+k}$, we get the best approximation ratios for both monotone and non-monotone submodular functions which are $(frac{1}{1+k}-epsilon)$ and $(frac{k}{(1+k)^2}-epsilon)$ respectively. While the parameter $epsilon$ exists for the trade-off between the approximation ratio and the time complexity. Therefore, our algorithm can handle larger scale of submodular maximization problems than existing algorithms.
We consider the problem of maximizing a monotone submodular function subject to a knapsack constraint. Our main contribution is an algorithm that achieves a nearly-optimal, $1 - 1/e - epsilon$ approximation, using $(1/epsilon)^{O(1/epsilon^4)} n log^2{n}$ function evaluations and arithmetic operations. Our algorithm is impractical but theoretically interesting, since it overcomes a fundamental running time bottleneck of the multilinear extension relaxation framework. This is the main approach for obtaining nearly-optimal approximation guarantees for important classes of constraints but it leads to $Omega(n^2)$ running times, since evaluating the multilinear extension is expensive. Our algorithm maintains a fractional solution with only a constant number of entries that are strictly fractional, which allows us to overcome this obstacle.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
