Variational Problem in Algorithms Design for DR-Submodular Maximization

The DR-submodular function, characterized by diminishing marginal returns property, has emerged as a topic of considerable interest across multiple disciplines, including operations research, theoretical computer science, and artificial intelligence. In this work, we demonstrate the variational problem and the Lyapunov-based framework to construct approximation algorithms for DR-submodular maximization problems. The methodological core involves leveraging variational problems to define parametric functions from which algorithms are derived and their approximation ratios are rigorously analyzed. As our first example, we design a double greedy algorithm for non-monotone DR-submodular maximization problems, considering both cardinality constraints and unconstrained scenarios. Through variational problems, our algorithm recovers the results presented in Buchbinder et al. (SIAM J Comput 44(5):1384–1402, 2015, [10]). For our second example, we introduce a variant of the Frank-Wolfe algorithm tailored for non-monotone DR-submodular maximization under down-closed convex constraints. Through variational problems, we not only recover the 0.385 approximation algorithm in Buchbinder and Feldman (Math Oper Res 44(3):988–1005, 2019, [7]) but also provide theoretical insights the performance implications of modifying existing 0.401 algorithms. Specifically, bypassing the recursion phase in existing 0.401 approximation algorithm (Buchbinder and Feldman, STOC 2024, p 1820-1831, 2024, [8]) induces a performance degradation, i.e., reducing the approximation ratio to 0.385.