Name
Title | ||
|---|---|---|
A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice |
Abstract | ||
|---|---|---|
Maximizing non-monotone submodular functions is one of the most important problems in submodular optimization. Let $$\mathbf {B}=(B_1, B_2,\ldots , B_n)\in {\mathbb {Z}}_+^n$$ be an integer vector and $$[\mathbf { B}]=\{(x_1,\dots ,x_n) \in {\mathbb {Z}}_+^n: 0\le x_k \le B_k, \forall 1\le k\le n\}$$ be the set of all non-negative integer vectors not greater than $$\mathbf {B}$$. A function $$f:[\mathbf { B}] \rightarrow {\mathbb {R}}$$ is said to be weak-submodular if $$f(\mathbf {x}+\delta \mathbf {1}_k)-f(\mathbf {x})\ge f(\mathbf {y}+\delta \mathbf {1}_k)-f(\mathbf {y})$$ for any $$k\in \{1,\dots ,n\}$$, any pair of $$\mathbf {x}, \mathbf {y}\in [\mathbf { B}]$$ such that $$\mathbf {x}\le \mathbf {y}$$ and $$x_k =y_k$$, and any $$\delta \in {\mathbb {Z}}_+$$ satisfying $$\mathbf {y}+\delta \mathbf {1}_k\in [\mathbf { B}]$$. Here $$\mathbf {1}_k$$ is the vector with the kth component equal to 1 and each of the others equals to 0. In this paper we consider the problem of maximizing a non-monotone and non-negative weak-submodular function on the bounded integer lattice without any constraint. We present an randomized algorithm with an approximation guarantee $$\frac{1}{2}$$ for the problem. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/s10878-020-00558-4 | Journal of Combinatorial Optimization |
Keywords | DocType | Volume |
Submodular, Non-monotone, Algorithm, Double greedy | Journal | 39 |
Issue | ISSN | Citations |
4 | 1382-6905 | 0 |
PageRank | References | Authors |
0.34 | 0 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Q. Q. Nong | 1 | 47 | 6.24 |
| Jiazhu Fang | 2 | 0 | 0.34 |
| Suning Gong | 3 | 5 | 1.84 |
| Ding-Zhu Du | 4 | 3497 | 283.06 |
| Yan Feng | 5 | 0 | 0.34 |
| Xiaoying Qu | 6 | 0 | 0.34 |