Variational Problem in Algorithms Design for DR-Submodular Maximization

Shengminjie Chen (), Dingzhu Du (), Xiaoming Sun (), Wenguo Yang () and Jialin Zhang ()
Additional contact information
Shengminjie Chen: Institute of Computing Technology, Chinese Academy of Sciences, State Key Lab of Processors
Dingzhu Du: University of Texas at Dallas, Department of Computer Science
Xiaoming Sun: Institute of Computing Technology, Chinese Academy of Sciences, State Key Lab of Processors
Wenguo Yang: University of Chinese Academy of Sciences, School of Mathematical Sciences
Jialin Zhang: Institute of Computing Technology, Chinese Academy of Sciences, State Key Lab of Processors

Chapter 3 in Convex and Variational Analysis with Applications, 2026, pp 49-75 from Springer

Abstract: Abstract 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.

Keywords: DR-Submodular maximization; Approximation algorithms; Variational problems (search for similar items in EconPapers)
Date: 2026
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-032-07860-5_3

Ordering information: This item can be ordered from
http://www.springer.com/9783032078605

DOI: 10.1007/978-3-032-07860-5_3

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().