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.

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

DR-Submodular Maximization and Its Application

  • Wenguo Yang,
  • Shengminjie Chen,
  • Xiaoming Sun

摘要

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.