Tight Algorithms for the Submodular Multiple Knapsack Problem
share
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 - ϵ)-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-ϵ) 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-ϵ). When the ratio between the maximum capacity and the minimum capacity of the bins is bounded by a constant, we provide a (1/2-ϵ)-approximation algorithm which is also combinatorial and deterministic. We can further boost the approximation ratio to (1 - 1 / e - ϵ) with the help of continuous greedy technique, which gives a tight randomized approximation algorithm for this case.
READ FULL TEXT