Maximizing stochastic set function under a matroid constraint from decomposition

doi:10.1007/s10878-024-01193-z

	Maximizing stochastic set function under a matroid constraint from decomposition
	Chen, Shengminjie 1,2,3; Du, Donglei 4; Yang, Wenguo 2; Gao, Suixiang 2
	2024-08-01
发表期刊	JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN	1382-6905
卷号	48 期号:1 页码:21
摘要	In this work, we focus on maximizing the stochastic DS decomposition problem. If the constraint is a uniform matroid, we design an adaptive policy, namely Myopic Parameter Conditioned Greedy, and prove its theoretical guarantee f(Theta(pi k))-(1-cG)g(Theta(pi k))>=(1-e-1)F(pi A & lowast;,Theta(pi k))-G(pi A & lowast;,Theta(pi k))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f(\varTheta (\pi _k))-(1-c_G)g(\varTheta (\pi _k))\ge (1-e<^>{-1})F(\pi <^>_A, \varTheta (\pi _k)) - G(\pi <^>_A,\varTheta (\pi _k))$$\end{document}, where F(pi A & lowast;,Theta(pi k))=E Theta[f(Theta(pi A & lowast;))\|Theta(pi k)]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F(\pi <^>_A, \varTheta (\pi _k)) = \mathbb {E}_{\varTheta }[f(\varTheta (\pi <^>_A)) \vert \varTheta (\pi _k)]$$\end{document}. When the constraint is a general matroid constraint, we design the Parameter Measured Continuous Conditioned Greedy to return a fractional solution. To round an integer solution from the fractional solution, we adopt the lattice contention resolution and prove that there is a (b,1-e-bb)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(b, \frac{1-e<^>{-b}}{b})$$\end{document} lattice CR scheme under a matroid constraint. Additionally, we adopt the pipage rounding to obtain a non-adaptive policy with the theoretical guarantee F(pi)-(1-cG)G(pi)>=(1-e-1)F(pi A & lowast;)-G(pi A & lowast;)-O(& varepsilon;)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F(\pi )-(1-c_G)G(\pi ) \ge (1-e<^>{-1}) F(\pi <^>_A) - G(\pi <^>_A) - O(\epsilon )$$\end{document} and utlize the (1,1-e-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1,1-e<^>{-1})$$\end{document}-lattice contention resolution scheme tau\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tau $$\end{document} to obtain an adaptive solution E tau similar to Lambda[f(tau(Theta(pi)))-(1-cG)g(tau(Theta(pi)))]>=(1-e-1)2F(pi A & lowast;,Theta(pi))-(1-e-1)G(pi A & lowast;,Theta(pi))-O(& varepsilon;)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {E}_{\tau \sim \varLambda } [f(\tau (\varTheta (\pi )))- (1-c_G) g(\tau (\varTheta (\pi )))] \ge (1-e<^>{-1})<^>2F(\pi <^>_A,\varTheta (\pi )) - (1-e<^>{-1}) G(\pi <^>_A,\varTheta (\pi )) -O(\epsilon )$$\end{document}. Since any set function can be expressed as the DS decomposition, our framework provides a method for solving the maximization problem of set functions defined on a random variable set.
关键词	Stochastic non-submodular maximization Weaker approximation Lattice contention resolution
DOI	10.1007/s10878-024-01193-z
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Interdisciplinary Applications ; Mathematics, Applied
WOS记录号	WOS:001278113300002
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/39682
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Yang, Wenguo
作者单位	1.Chinese Acad Sci, Inst Comp Technol, State Key Lab Processors, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China 3.Univ Chinese Acad Sci, Sch Comp Sci & Technol, Beijing 100049, Peoples R China 4.Univ New Brunswick, Fac Management, Fredericton, NB E3B 5A3, Canada
推荐引用方式 GB/T 7714	Chen, Shengminjie,Du, Donglei,Yang, Wenguo,et al. Maximizing stochastic set function under a matroid constraint from decomposition[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION,2024,48(1):21.
APA	Chen, Shengminjie,Du, Donglei,Yang, Wenguo,&Gao, Suixiang.(2024).Maximizing stochastic set function under a matroid constraint from decomposition.JOURNAL OF COMBINATORIAL OPTIMIZATION,48(1),21.
MLA	Chen, Shengminjie,et al."Maximizing stochastic set function under a matroid constraint from decomposition".JOURNAL OF COMBINATORIAL OPTIMIZATION 48.1(2024):21.