Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMultilinear extension of $k$-submodular functions
79
0
0.0
(
0
)
Added by
Huanjian Zhou
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A $k$-submodular function is a function that given $k$ disjoint subsets outputs a value that is submodular in every orthant. In this paper, we provide a new framework for $k$-submodular maximization problems, by relaxing the optimization to the continuous space with the multilinear extension of $k$-submodular functions and a variant of pipage rounding that recovers the discrete solution. The multilinear extension introduces new techniques to analyze and optimize $k$-submodular functions. When the function is monotone, we propose almost $frac{1}{2}$-approximation algorithms for unconstrained maximization and maximization under total size and knapsack constraints. For unconstrained monotone and non-monotone maximization, we propose an algorithm that is almost as good as any combinatorial algorithm based on Iwata, Tanigawa, and Yoshidas meta-framework ($frac{k}{2k-1}$-approximation for the monotone case and $frac{k^2+1}{2k^2+1}$-approximation for the non-monotone case).
rate research
Read More
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.
The problem of maximizing a non-negative submodular function was introduced by Feige, Mirrokni, and Vondrak [FOCS07] who provided a deterministic local-search based algorithm that guarantees an approximation ratio of $frac 1 3$, as well as a randomized $frac 2 5$-approximation algorithm. An extensive line of research followed and various algorithms with improving approximation ratios were developed, all of them are randomized. Finally, Buchbinder et al. [FOCS12] presented a randomized $frac 1 2$-approximation algorithm, which is the best possible. This paper gives the first deterministic algorithm for maximizing a non-negative submodular function that achieves an approximation ratio better than $frac 1 3$. The approximation ratio of our algorithm is $frac 2 5$. Our algorithm is based on recursive composition of solutions obtained by the local search algorithm of Feige et al. We show that the $frac 2 5$ approximation ratio can be guaranteed when the recursion depth is $2$, and leave open the question of whether the approximation ratio improves as the recursion depth increases.
Motivated by applications in machine learning, such as subset selection and data summarization, we consider the problem of maximizing a monotone submodular function subject to mixed packing and covering constraints. We present a tight approximation algorithm that for any constant $epsilon >0$ achieves a guarantee of $1-frac{1}{mathrm{e}}-epsilon$ while violating only the covering constraints by a multiplicative factor of $1-epsilon$. Our algorithm is based on a novel enumeration method, which unlike previous known enumeration techniques, can handle both packing and covering constraints. We extend the above main result by additionally handling a matroid independence constraints as well as finding (approximate) pareto set optimal solutions when multiple submodular objectives are present. Finally, we propose a novel and purely combinatorial dynamic programming approach that can be applied to several special cases of the problem yielding not only {em deterministic} but also considerably faster algorithms. For example, for the well studied special case of only packing constraints (Kulik {em et. al.} [Math. Oper. Res. `13] and Chekuri {em et. al.} [FOCS `10]), we are able to present the first deterministic non-trivial approximation algorithm. We believe our new combinatorial approach might be of independent interest.
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.
Given a separation oracle $mathsf{SO}$ for a convex function $f$ that has an integral minimizer inside a box with radius $R$, we show how to find an exact minimizer of $f$ using at most (a) $O(n (n + log(R)))$ calls to $mathsf{SO}$ and $mathsf{poly}(n, log(R))$ arithmetic operations, or (b) $O(n log(nR))$ calls to $mathsf{SO}$ and $exp(n) cdot mathsf{poly}(log(R))$ arithmetic operations. When the set of minimizers of $f$ has integral extreme points, our algorithm outputs an integral minimizer of $f$. This improves upon the previously best oracle complexity of $O(n^2 (n + log(R)))$ for polynomial time algorithms obtained by [Grotschel, Lovasz and Schrijver, Prog. Comb. Opt. 1984, Springer 1988] over thirty years ago. For the Submodular Function Minimization problem, our result immediately implies a strongly polynomial algorithm that makes at most $O(n^3)$ calls to an evaluation oracle, and an exponential time algorithm that makes at most $O(n^2 log(n))$ calls to an evaluation oracle. These improve upon the previously best $O(n^3 log^2(n))$ oracle complexity for strongly polynomial algorithms given in [Lee, Sidford and Wong, FOCS 2015] and [Dadush, Vegh and Zambelli, SODA 2018], and an exponential time algorithm with oracle complexity $O(n^3 log(n))$ given in the former work. Our result is achieved via a reduction to the Shortest Vector Problem in lattices. We show how an approximately shortest vector of certain lattice can be used to effectively reduce the dimension of the problem. Our analysis of the oracle complexity is based on a potential function that captures simultaneously the size of the search set and the density of the lattice, which we analyze via technical tools from convex geometry.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
