In this chapter, we introduce techniques for maximizing non-monotone DR-submodular functions over the integer lattice. Functions defined over the integer lattice exhibit a submodular property akin to that of set functions. DR submodularity represents a further extension of submodularity tailored for functions over the integer lattice, capturing the diminishing returns property. Such functions find widespread applications in fields such as machine learning, social networks, and wireless networks. Techniques developed for maximizing submodular set functions can be adapted to DR-submodular function maximization. For instance, the double greedy algorithm, which solves submodular maximization, achieves a \(1/2\) -approximation ratio with a runtime of \(O(nB)\) for DR-submodular maximization, where n denotes the size of the ground set and B is the integer bound of a coordinate. This chapter presents a \(1/2\) -approximate binary search double greedy algorithm with improved time complexity of \(O(n\log B)\) . We illustrate an application scenario focusing on profit maximization in social networks, aiming to optimize the net profit derived from product promotion activities.

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

Non-monotone DR-Submodular Maximization

  • Shuyang Gu

摘要

In this chapter, we introduce techniques for maximizing non-monotone DR-submodular functions over the integer lattice. Functions defined over the integer lattice exhibit a submodular property akin to that of set functions. DR submodularity represents a further extension of submodularity tailored for functions over the integer lattice, capturing the diminishing returns property. Such functions find widespread applications in fields such as machine learning, social networks, and wireless networks. Techniques developed for maximizing submodular set functions can be adapted to DR-submodular function maximization. For instance, the double greedy algorithm, which solves submodular maximization, achieves a \(1/2\) -approximation ratio with a runtime of \(O(nB)\) for DR-submodular maximization, where n denotes the size of the ground set and B is the integer bound of a coordinate. This chapter presents a \(1/2\) -approximate binary search double greedy algorithm with improved time complexity of \(O(n\log B)\) . We illustrate an application scenario focusing on profit maximization in social networks, aiming to optimize the net profit derived from product promotion activities.