arrow
Return

Regularized two-stage submodular maximization under streaming

delete2022-03-14
delete2
PRE
AI
R
Ruiqi Yang
D
Dachuan Xu
郭
郭龙坤 (Longkun Guo)
D
Dongmei Zhang *
DOI:10.1007/s11432-020-3420-9delete
deleteOriginal
deleteShare
deleteSave
Abstract

Abstract

En 中文
In the problem of maximizing regularized two-stage submodular functions in streams, we assemble a family F of m functions each of which is submodular and is visited in a streaming style that an element is visited for only once. The aim is to choose a subset S of size at most l from the element stream V, so as to maximize the average maximum value of these functions restricted on S with a regularized modular term. The problem can be formally casted as max(S subset of V, vertical bar S vertical bar <= l) 1/m Sigma(m)(i=1) max(T subset of S, vertical bar T vertical bar) (<=) (k) [f(i)(T) - c(T)], where : V -> R+ is a non-negative modular function and f(i) : 2(V) -> R+, for all i is an element of {1, ..., m} is a non-negative mono- tone non-decreasing submodular function. The well-studied regularized problem of max(S subset of V,) (vertical bar S vertical bar <= k) f(S) - c(S) is exactly a special case of the above regularized two-stage submodular maximization by setting m = 1 and l = k. Although f(.) - c(.) is submodular, it is potentially negative and non-monotone and admits no constant multiplicative factor approximation. Therefore, we adopt a slightly weaker notion of approximation which constructs S such that f (S) - c(S) >= rho . f (O) - c(O) holds against optimum solution O for some rho is an element of (0, 1). Eventually, we devise a streaming algorithm by employing the distorted threshold technique, achieving a weaker approximation ratio with rho = 0.2996 for the discussed regularized two-stage model.
Keywords:
submodular maximization
streaming model
two-stage
threshold technique
approximation algorithms

Journal

Science China Information Sciences cover
Science China Information Sciences
IF:
7.6
Papers:
4.9K
Citations:
1.2W

Organization

Beijing University of Technology cover
Beijing University of Technology
Scholars:
4.1K
Papers: 1.2K
Citations: 1.8W
qilu university of technology cover
qilu university of technology
Scholars:
1.3K
Papers: 372
Citations: 7.3K
University of Chinese Academy of Sciences cover
University of Chinese Academy of Sciences
Scholars:
2.5K
Papers: 1.0K
Citations: 1.3K
researcher View more organizations
Cited Papers

Cited Papers

Association of implantable defibrillator therapy risk with body mass index in systolic heart failure
err2013-07-01
err0
PREAI
errMitul Gandhi; Todd M. Koelling; Frank Pelosi; Shaun P. Patel; Brandon M. Wojcik; Laura E. Horwood; Audrey H. Wu
errShare
errSave
Health and economic impacts of Vaccae vaccination incorporating active case finding in India and South Africa: a modelling study
err2024-09-20
err0
errOAAI
errWan-Lu Yue; Pei-Yao Zhai; Jun-Jie Mao; Jun-Feng Ma; Wen-Long Ren; Ting Jiang; Bin Zhang; Xun Zhuang; Jian Feng; Xiao Zang; Gang Qin
errShare
errSave
Recognition of oxidized DNA bases by sera of patients with inflammatory diseases
err1993-05-01
err0
PREAI
errKrystyna Frenkel; Jerzy Karkoszka; Eung Kim; Emanuela Taioli
errShare
errSave
Impairment of PI3K/AKT and WNT/β-catenin pathways in bone marrow mesenchymal stem cells isolated from patients with myelodysplastic syndromes
err2016-01-01
err0
errOAAI
errGiulia Falconi; Emiliano Fabiani; Luana Fianchi; Marianna Criscuolo; Chiara Spertilli Raffaelli; Silvia Bellesi; Stefan Hohaus; Maria Teresa Voso; Francesco D’Alò; Giuseppe Leone
errShare
errSave
researcher View more