Modified Greedy Algorithm for Monotone Submodular Maximization with Knapsack and Partition Matroid Constraints
摘要
In this paper, we study the monotone submodular maximization problem with a knapsack constraint and a partition matroid constraint, where the ground set is partitioned into k disjoint classes. We propose the maximum imbalance parameter \(\lambda \) , defined as the maximum ratio of cost values between any two elements within the same class. We design a modified greedy algorithm which returns the better solution between the constructed greedy solution and a single element. We show that this algorithm can achieve an approximation ratio of \(\min \{ \frac{1}{1+\lambda }( 1-e^{-\frac{1+\lambda }{2}} ) ,\frac{1}{2+\lambda } \}\) . In particular, when all elements within each class have identical cost values, i.e., \(\lambda =1\) , the algorithm obtains an approximation guarantee of \(\frac{1}{2}(1-e^{-1}) \approx 0.316\) .