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. 13 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 consider the case when the number of bins is a constant and provide a simple combinatorial deterministic algorithm with an optimal (1-1/ e) ratio. Previously, a randomized approximation algorithm obtained a (1 - 1/ e-\epsilon) approximation ratio based on the involved continuous greedy technique. We then generalize the result to arbitrary number of bins. When the capacity of bins are identical, we design a combinatorial and deterministic algorithm which achieves an almost 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 boost this algorithmto a (1-1/e-\epsilon) randomized algorithm for the general case, thus matching the result of Fairstein et al. 13 .
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 or 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 a tight (1-1/ e-\epsilon) deterministic algorithm for SMKP. Our algorithm is based on reducing SMKP to an exponential-size submodular maximizaion problem over a special partition matroid which enjoys a tight deterministic algorithm. We develop several techniques to mimic the algorithm, leading to a tight deterministic approximation for SMKP .
R
monotone/
(monotone or
A
)
R
13
(ESA20)
R
deterministic algorithms with improved approximation ratios for SMKP. We first consider the case when the number of bins is a constant and provide a simple combinatorial deterministic algorithm with an optimal
a tight
D
e) ratio. Previously, a randomized approximation algorithm obtained a (1 - 1/
D
approximation ratio based on the involved continuous greedy technique. We then generalize the result to arbitrary number of bins. When the capacity of bins are identical, we design a combinatorial and deterministic algorithm which achieves an almost 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 boost this algorithmto a (1-1/e-\epsilon) randomized algorithm for the general case, thus matching the result of Fairstein et al.
R
13
deterministic algorithm for SMKP. Our algorithm is based on reducing SMKP to an exponential-size submodular maximizaion problem over a special partition matroid which enjoys a tight deterministic algorithm. We develop several techniques to mimic the algorithm, leading to a tight deterministic approximation for SMKP