Non-monotone DR-Submodular Maximization
摘要
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.