DR-Submodular Maximization and Its Application

Wenguo Yang (), Shengminjie Chen () and Xiaoming Sun ()
Additional contact information
Wenguo Yang: University of Chinese Academy of Sciences, School of Mathematical Sciences
Shengminjie Chen: Chinese Academy of Sciences, State Key Lab of Processors, Institute of Computing Technology
Xiaoming Sun: Chinese Academy of Sciences, State Key Lab of Processors, Institute of Computing Technology

A chapter in Theory, Algorithms, and Experiments in Applied Optimization, 2025, pp 393-444 from Springer

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

Keywords: DR-submodular maximization; Approximation algorithms; Diminishing marginal returns (search for similar items in EconPapers)
Date: 2025
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-031-91357-0_18

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

DOI: 10.1007/978-3-031-91357-0_18

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 ().