arrow
返回

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
delete原文链接
delete分享
delete收藏
摘要

摘要

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.
Keyword:
submodular maximization
streaming model
two-stage
threshold technique
approximation algorithms

期刊

Science China Information Sciences 封面图
Science China Information Sciences
IF:
7.6
论文数:
4.9K
被引数:
1.2W

机构

北京工业大学 封面图
北京工业大学
学者数:
4.1K
论文数: 1.2K
被引数: 1.8W
齐鲁工业大学 封面图
齐鲁工业大学
学者数:
1.3K
论文数: 372
被引数: 7.3K
中国科学院大学 封面图
中国科学院大学
学者数:
2.5K
论文数: 1.0K
被引数: 1.3K
学者 查看更多机构
引用论文

引用论文

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
err分享
err收藏
err分享
err收藏
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
err分享
err收藏
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
err分享
err收藏
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
err分享
err收藏
学者 查看更多内容