A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice

Qingqin Nong, Jiazhu Fang, Suning Gong (), Dingzhu Du, Yan Feng and Xiaoying Qu
Additional contact information
Qingqin Nong: Ocean University of China
Jiazhu Fang: Ocean University of China
Suning Gong: Ocean University of China
Dingzhu Du: University of Texas
Yan Feng: Ocean University of China
Xiaoying Qu: Ocean University of China

Journal of Combinatorial Optimization, 2020, vol. 39, issue 4, No 11, 1208-1220

Abstract: 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$$B=(B1,B2,…,Bn)∈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\}$$[B]={(x1,⋯,xn)∈Z+n:0≤xk≤Bk,∀1≤k≤n} be the set of all non-negative integer vectors not greater than $$\mathbf {B}$$B. A function $$f:[\mathbf { B}] \rightarrow {\mathbb {R}}$$f:[B]→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})$$f(x+δ1k)-f(x)≥f(y+δ1k)-f(y) for any $$k\in \{1,\dots ,n\}$$k∈{1,⋯,n}, any pair of $$\mathbf {x}, \mathbf {y}\in [\mathbf { B}]$$x,y∈[B] such that $$\mathbf {x}\le \mathbf {y}$$x≤y and $$x_k =y_k$$xk=yk, and any $$\delta \in {\mathbb {Z}}_+$$δ∈Z+ satisfying $$\mathbf {y}+\delta \mathbf {1}_k\in [\mathbf { B}]$$y+δ1k∈[B]. Here $$\mathbf {1}_k$$1k 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}$$12 for the problem.

Keywords: Submodular; Non-monotone; Algorithm; Double greedy (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00558-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:jcomop:v:39:y:2020:i:4:d:10.1007_s10878-020-00558-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00558-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().