Maximize a monotone function with a generic submodularity ratio

Generic submodularity ratio γ is a general measurement to characterize how close a nonnegative monotone set function is to be submodular. In this paper, we make a systematic analysis of greedy algorithms for maximizing a monotone and normalized set function with a generic submodularity ratio γ under Cardinality constraints, Knapsack constraints, Matroid constraints and K-intersection constraints.

Authors

• Suning Gong
• Qingqin Nong
• Tao Sun Beihang University
• Qizhi Fang Ocean University of China
• Dingzhu Du
• Xiaoyu Shao

Keywords

• Non-submodular
• Greedy
• Independent system