Submodular function maximization has been a central topic in the theoretical computer science community over the last decade. A plenty of well-performed approximation algorithms have been designed for the maximization of monotone/non-monotone submodular functions over a variety of constraints. In this paper, we consider the submodular multiple knapsack problem (SMKP), which is the submodular version of the well-studied multiple knapsack problem (MKP). Roughly speaking, the problem asks to maximize a monotone submodular function over multiple bins (knapsacks). Despite lots of known results in the field of submodular maximization, surprisingly, it remains unknown whether or not this problem enjoys the well-known tight (1 - 1 / e )-approximation . In this paper, we answer this question affirmatively by proposing tight (1 - 1 / e - \epsilon)-approximation algorithms for this problem in most cases . We first considered the case when the number of bins is a constant. Previously a randomized approximation algorithm can obtain approximation ratio (1 - 1/e-\epsilon) based on the involved continuous greedy technique. Here we provide a simple combinatorial deterministic algorithm with ratio (1-1/e) by directly applying the greedy technique. We then generalized the result to arbitrary number of bins. When the capacity of bins are identical, we design a combinatorial and deterministic algorithm which can achieve the tight approximation ratio (1 - 1 / e-\epsilon). When the ratio between the maximum capacity and the minimum capacity of the bins is bounded by a constant , we provide a (1/2-\epsilon)-approximation algorithm which is also combinatorial and deterministic. We can further boost the approximation ratio to (1 - 1 / e - \epsilon ) with the help of continuous greedy technique, which gives a tight randomized approximation algorithm for this case .
Submodular function maximization has been a central topic in the theoretical computer science community over the last decade. Plenty of well-performing approximation algorithms have been designed for the maximization of monotone/non-monotone submodular functions over a variety of constraints. In this paper, we consider the submodular multiple knapsack problem (SMKP), which is the submodular version of the well-studied multiple knapsack problem (MKP). Roughly speaking, the problem asks to maximize a monotone submodular function over multiple bins (knapsacks). Recently, Fairstein et al. (ESA20) presented a tight (1-1 / e-\epsilon )-approximation randomized algorithm for SMKP. Their algorithm is based on the continuous greedy technique which inherently involves randomness. However, the deterministic algorithm of this problem has not been understood very well previously. In this paper, we present deterministic algorithms with improved approximation ratios for SMKP . We first considered the case when the number of bins is a constant. Previously a randomized approximation algorithm can obtain approximation ratio (1 - 1/e-\epsilon) based on the involved continuous greedy technique. Here we provide a simple combinatorial deterministic algorithm with ratio (1-1/e) by directly applying the greedy technique. We then generalized the result to arbitrary number of bins. When the capacity of bins are identical, we design a combinatorial and deterministic algorithm which can achieve the tight approximation ratio (1 - 1 / e-\epsilon). In the general case , we provide a (1/2-\epsilon)-approximation algorithm which is also combinatorial and deterministic. We finally show a 1-1 / e-\epsilon randomized algorithm for the general case, thus achieving the same result as Fairstein et al. (ESA20) .
R
A plenty of well-performed
Plenty of well-performing
R
Despite lots of known results in the field of submodular maximization, surprisingly, it remains unknown whether or not this problem enjoys the well-known tight (1 - 1
Recently, Fairstein et al. (ESA20) presented a tight (1-1
R
e
e-\epsilon
R
.
randomized algorithm for SMKP. Their algorithm is based on the continuous greedy technique which inherently involves randomness. However, the deterministic algorithm of this problem has not been understood very well previously.
R
answer this question affirmatively by proposing tight (1 - 1 / e - \epsilon)-approximation algorithms for this problem in most cases
present deterministic algorithms with improved approximation ratios for SMKP
R
When the ratio between the maximum capacity and the minimum capacity of the bins is bounded by a constant
In the general case
R
can further boost the approximation ratio to (1 - 1
finally show a 1-1
R
e - \epsilon ) with the help of continuous greedy technique, which gives a tight randomized approximation algorithm for this case
e-\epsilon randomized algorithm for the general case, thus achieving the same result as Fairstein et al. (ESA20)