Author name cluster

Suning Gong

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

TCS Journal 2021 Journal Article

Maximize a monotone function with a generic submodularity ratio

Suning Gong
Qingqin Nong
Tao Sun
Qizhi Fang
Dingzhu Du
Xiaoyu Shao

Generic submodularity ratio γ is a general measurement to characterize how close a nonnegative monotone set function is to be submodular. In this paper, we make a systematic analysis of greedy algorithms for maximizing a monotone and normalized set function with a generic submodularity ratio γ under Cardinality constraints, Knapsack constraints, Matroid constraints and K-intersection constraints.

Details DOI

TCS Journal 2020 Journal Article

A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function

Qingqin Nong
Jiazhu Fang
Suning Gong
Yan Feng
Xiaoying Qu

In this paper we consider the problem of maximizing a non-monotone and non-negative DR-submodular function on a bounded integer lattice [ B → ] = { ( x 1, …, x n ) ∈ Z + n: 0 ≤ x k ≤ B k, ∀ 1 ≤ k ≤ n } without any constraint, where B → = ( B 1, …, B n ) ∈ Z + n. We design an algorithm for the problem and measure its performance by its approximation ratio and the number of value oracle queries it needs, where the latter one is the dominating term in the running time of an algorithm. It has been showed that, for the problem considered, any algorithm achieving an approximation ratio greater than 1 2 requires an exponential number of value oracle queries. In the literature there are two algorithms that reach 1 2 approximation guarantee. The first algorithm needs O ( n | | B | | ∞ ) oracle queries. The second one reduces its number of oracle queries to O ( n max ⁡ { 1, log ⁡ | | B → | | ∞ } ) but it needs large storage. In this paper we present a randomized approximation algorithm that has an approximation guarantee of 1 2, calls O ( n max ⁡ { 1, log ⁡ | | B → | | ∞ } ) oracle queries and does not need large storage, improving the results of the literature.

Details DOI

TCS Journal 2020 Journal Article

General Rumor Blocking: An efficient random algorithm with martingale approach

Qizhi Fang
Xin Chen
Qingqin Nong
Zongchao Zhang
Yongchang Cao
Yan Feng
Tao Sun
Suning Gong

Rumor Blocking, an important optimization problem in social network, has been extensively studied in the literature. Given social network G = ( V, E ) and rumor seed set A, the goal is asking for k protector seeds that protect the largest expected number of social individuals by truth. However, the source of rumor is always uncertain, rather than being predicted or being known in advance in the real situations, while rumor spreads like wildfire on the Internet. This paper presents General Rumor Blocking with unpredicted rumor seed set (randomized A) and various personal profits while being protected (weights of nodes in V). We first show that the objective function of this problem is non-decreasing and submodular, and thus a ( 1 − 1 / e ) approximate solution can be returned by greedy approach. We then propose an efficient random algorithm R-GRB which returns a ( 1 − 1 / e − ε ) approximate solution with at least 1 − n − ℓ probability. We show that it runs in O ( m ( n − r ) ( k log ⁡ ( n − r ) + ℓ log ⁡ n ) / ε 2 ) expected time, where m = | E |, n = | V |, r = | A | and k is the number of protector seeds. Finally, we conduct extensive experiments to evaluate the R-GRB and show that it is superior in both theory and experiment.

Details DOI