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\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Modified Greedy Algorithm for Monotone Submodular Maximization with Knapsack and Partition Matroid Constraints

  • Dongkai Xu,
  • Jianhua Yuan,
  • Zhongzheng Tang

摘要

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\) .