DR-Submodular Maximization and Its Application
摘要
The DR-submodular function, a class of functions characterized by diminishing marginal returns property, has garnered significant attention in many fields, notably artificial intelligence and social network analysis. We commence with a concise yet comprehensive overview of the definitions and properties of DR-submodular functions, encompassing both in set functions and continuously differentiable functions. While minimizing an unconstraint DR-submodular function is polynomially solvable, maximizing the DR-submodular function is NP-hard. Consequently, we turn to how to maximize DR-submodular functions. Our main contribution is to retrospect a spectrum of algorithms tailored for this purpose, spanning both discrete and continuous domains, and provide proof sketches to illustrate their approximation ratios. At last, we briefly outline some potential directions and applications for the DR-submodular maximization problem.