We consider a knapsack-constrained maximization problem of a nonnegative monotone dr-submodular function f over a bounded integer lattice [B] in R-+(n), max{f (x) : x is an element of [B] and Sigma(n)(i=1) x(i)c(i) &l...
详细信息
We consider a knapsack-constrained maximization problem of a nonnegative monotone dr-submodular function f over a bounded integer lattice [B] in R-+(n), max{f (x) : x is an element of [B] and Sigma(n)(i=1) x(i)c(i) <= 1}, where n is the cardinality of a ground set N and c(.) is a cost function defined on N. Soma and Yoshida [Math. Program., 172 (2018), pp. 539-563] present a (1 - e(-1) - O(epsilon))-approximation algorithm for this problem by combining threshold greedy algorithm with partial element enumeration technique. Although the approximation ratio is almost tight, their algorithm runs in O(n(3)/epsilon(3) log(3) tau[log(3) parallel to B parallel to(infinity) + n/epsilon log parallel to B parallel to(infinity) log 1/epsilon c(min)]) time, where c(min) = min(i) c(i) and tau is the /ratio of the maximum value of f to the minimum nonzero increase in the value of f . Besides, Ene and Nguyen [arXiv:1606.08362, 2016] indirectly give a (1 - e(-1) - O(epsilon))-approximation algorithm with O((1/epsilon)(O(1/epsilon 4))n log parallel to B parallel to(infinity) log(2) (n log parallel to B parallel to(infinity))) time. But their algorithm is random. In this paper, we make full use of the dr-submodularity over a bounded integer lattice, carry forward the greedy idea in the continuous process and provide a simple deterministic rounding method so as to obtain a feasible solution of the original problem without loss of objective value. We present a deterministic algorithm and theoretically reduce its running time to a new record, O((1/epsilon)(O(1 /epsilon 5)) . n log 1/c(min) log parallel to B parallel to(infinity)), with the same approximate ratio.
Profit maximization (PM) is to select a subset of users as seeds for viral marketing in online social networks, which balances between the cost and the profit from influence spread. We extend PM to formulate a continu...
详细信息
Profit maximization (PM) is to select a subset of users as seeds for viral marketing in online social networks, which balances between the cost and the profit from influence spread. We extend PM to formulate a continuous PM under the general marketing strategies (CPM-MS) problem, whose domain is on integer lattices. The objective function of our CPM-MS is dr-submodular, but nonmonotone. It is a typical case of unconstrained dr-submodular maximization (UDSM) problem, and taking it as a starting point, we study UDSM systematically in this article, which is very different from those studied by existing researchers. First, we introduce the lattice-based double greedy algorithm, which can obtain a constant approximation guarantee. However, there is a strict and unrealistic condition that requiring the objective value is nonnegative on the whole domain or else no theoretical bounds. Thus, we propose a lattice-based iterative pruning technique. It can shrink the search space effectively, thereby greatly increasing the possibility of satisfying the nonnegative objective function on this smaller domain without losing approximation ratio. Then, to overcome the difficulty to estimate the objective value of CPM-MS, we adopt reverse sampling strategies and combine it with lattice-based double greedy, including pruning, without losing its performance but reducing its running time. The entire process can be considered as a general framework to solve the UDSM problem, especially for applying to social networks. Finally, we conduct experiments on several real data sets to evaluate the effectiveness and efficiency of our proposed algorithms.
submodularmaximization is a NP-hard combinatorial optimization problem regularly used in machine learning and data mining with large-scale data sets. To quantify the running time of approximation algorithms, the quer...
详细信息
submodularmaximization is a NP-hard combinatorial optimization problem regularly used in machine learning and data mining with large-scale data sets. To quantify the running time of approximation algorithms, the query complexity and adaptive complexity are two important measures, where the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially many function evaluations in parallel. These two concepts reasonably quantify the efficiency and practicability of parallel computation. In this paper, we consider the problem of maximizing a nonnegative monotone dr-submodular function over a bounded integer lattice with a cardinality constraint in a value oracle model. Prior to our work, Soma and Yoshida (Math Program 172:539-563, 2018) have studied this problem and present an approximation algorithm with almost optimal approximate ratio and the same adaptivity and query complexity. We develop two novel algorithms, called low query algorithm and low adaptivity algorithm, which have approximation ratios equal to Soma and Yoshida (2018), but reach a new record of query complexity and adaptivity. As for methods, compared with the threshold greedy in Soma and Yoshida (2018), the low query algorithm reduces the number of possible thresholds and improves both the adaptivity and query complexity. The low adaptivity algorithm further integrates a vector sequencing technique to accelerate adaptive complexity in an exponential manner while only making logarithmic sacrifices on oracle queries.
In this work, we investigate the problem of maximizing nonmonotone dr-submodular function (possibly negative) subject to cardinality constraints on an integer lattice space. We propose a M-Threshold Decrease Algorithm...
详细信息
In this work, we investigate the problem of maximizing nonmonotone dr-submodular function (possibly negative) subject to cardinality constraints on an integer lattice space. We propose a M-Threshold Decrease Algorithm that uses a compensation constant.. from a special decomposition h(x) = f(x) - g(x), which achieves a 1 - e(-delta) - epsilon approximation guarantee. To ensure that the algorithm ends in finite time, the supremum of delta is delta(epsilon) = epsilon max(s is an element of Omega) h(chi(s)vertical bar 0)/2k max(s is an element of Omega) g(chi(s)vertical bar 0)+epsilon max(s is an element of Omega) h(chi(s) 0). If max(s is an element of Omega) h(chi(s vertical bar vertical bar)0) > 2k max(s is an element of Omega) g(chi(s)vertical bar 0), there exists epsilon* = arg max(epsilon is an element of(0,1)) 1 - e(-delta(epsilon)) - epsilon such that 1 - e(-delta(epsilon)*()) - epsilon* > 0. This implies that there is a valid delta such that 1 - e(-delta) > 0. To accelerate the algorithm, we employ a random subset to replace the ground set and propose a Random M-Threshold Decrease Algorithm, where delta(epsilon) = epsilon r max(s is an element of Omega) h(chi(s)vertical bar 0)/2k max(s is an element of Omega) g(chi(s)vertical bar 0)+[k(n-r)+epsilon r] max(s is an element of Omega) h(chi(s vertical bar)0) with being the size of the random subset and n being the size of the ground set. Furthermore, we demonstrate that, based on the dr-ratio gamma(d) and the DS decomposition, the M-Threshold Decrease Algorithm is also suitable for solving the monotone non-dr-submodular maximization problem, achieving a 1 - e-(gamma d delta) - O(epsilon) approximation guarantee. Because gamma(d) is a challenging metric to calculate, we refine the M-Threshold Decrease Algorithm, which can return an estimate of gamma(d). To the best of our knowledge, this is the first time that a single factor approximation ratio has been proposed for the nonmonotone dr-submodular maximization problem
In this work, we focus on maximizing the ratio of two monotone dr-submodular functions on the integer lattice. It is neither submodular nor supermodular. We prove that the Threshold Decrease Algorithm is a 1 - e(-(1-k...
详细信息
In this work, we focus on maximizing the ratio of two monotone dr-submodular functions on the integer lattice. It is neither submodular nor supermodular. We prove that the Threshold Decrease Algorithm is a 1 - e(-(1-kg)) - e approximation ratio algorithm. Additionally, we construct the relationship between maximizing the ratio of two monotone dr-submodular functions and maximizing the difference of two monotone dr-submodular functions on the integer lattice. Based on this relationship, we combine the dichotomy technique and Threshold Decrease Algorithm to solve maximizing the difference of two monotone dr-submodular functions on the integer lattice and prove its approximation ratio is f (x)-g(x) ? 1-e(-(1-kg)) f (x*)-g(x*)- e. To the best of our knowledge, before us, there was no work to focus on maximizing the ratio of two monotone dr-submodular functions on integer lattice by using the Threshold Decrease Algorithm.
We consider the problem of maximizing the multilinear extension of a submodular function subject a single matroid constraint or multiple packing constraints with a small number of adaptive rounds of evaluation queries...
详细信息
ISBN:
(纸本)9781450367059
We consider the problem of maximizing the multilinear extension of a submodular function subject a single matroid constraint or multiple packing constraints with a small number of adaptive rounds of evaluation queries. We obtain the first algorithms with low adaptivity for submodularmaximization with a matroid constraint. Our algorithms achieve a 1 - 1/e - epsilon approximation for monotone functions and a 1/e - epsilon approximation for non-monotone functions, which nearly matches the best guarantees known in the fully adaptive setting. The number of rounds of adaptivity is O(log(2) n/epsilon(3)), which is an exponential speedup over the existing algorithms. We obtain the first parallel algorithm for non-monotone submodularmaximization subject to packing constraints. Our algorithm achieves a 1/e - epsilon approximation using O(log(n/epsilon) log(1/epsilon) log(n + m)/epsilon(2)) parallel rounds, which is again an exponential speedup in parallel time over the existing algorithms. For monotone functions, we obtain a 1-1/e - epsilon approximation inO(log(n/epsilon) logm/epsilon(2)) parallel rounds. The number of parallel rounds of our algorithm matches that of the state of the art algorithm for solving packing LPs with a linear objective (Mahoney et al., 2016). Our results apply more generally to the problem of maximizing a diminishing returns submodular (dr-submodular) function.
暂无评论