Name
Abstract | ||
|---|---|---|
A function $f: mathbb{Z}_+^E rightarrow mathbb{R}_+$ is DR-submodular if it satisfies $f(bx + chi_i) -f (bx) ge f(by + chi_i) - f(by)$ for all $bxle by, iin E$. Recently, the problem of maximizing a DR-submodular function $f: mathbb{Z}_+^E rightarrow mathbb{R}_+$ subject to a budget constraint $|bx|_1 leq B$ as well as additional constraints has received significant attention cite{SKIK14,SY15,MYK15,SY16}. In this note, we give a generic reduction from the DR-submodular setting to the submodular setting. The running time of the reduction and the size of the resulting submodular instance depends only emph{logarithmically} on $B$. Using this reduction, one can translate the results for unconstrained and constrained submodular maximization to the DR-submodular setting for many types of constraints in a unified manner. |
Year | Venue | Field |
|---|---|---|
2016 | arXiv: Data Structures and Algorithms | Discrete mathematics,Combinatorics,Lattice (order),Submodular set function,Submodular maximization,Mathematics |
DocType | Volume | Citations |
Journal | abs/1606.08362 | 5 |
PageRank | References | Authors |
0.43 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alina Ene | 1 | 409 | 25.47 |
| Huy L. Nguyen | 2 | 376 | 32.33 |