Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions

In this paper, we study the problem of maximizing the Difference of two Submodular (DS) functions in the streaming model, where elements in the ground set arrive one at a time in an arbitrary order. We present one-pass streaming algorithms for both the unconstrained and cardinality-constrained problems. Our analysis shows that the algorithms we propose are able to produce solutions with provable approximation guarantees. To the best of our knowledge, this is the first theoretical guarantee for the DS maximization problem in the streaming model. In addition, we study the function maximization problem under a cardinality constraint, where the underlying objective function is a γ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma $$\end{document}-weakly DR-submodular function, in the streaming setting. We propose a one-pass streaming algorithm, which achieves an approximation ratio of γ/(1+γ)-ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma /(1 + \gamma ) - \epsilon $$\end{document}. Since the sum of suBmodular and suPermodular (BP) functions can be regarded as a (1-κg)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1 - \kappa ^g)$$\end{document}-weakly DR-submodular function, we obtain a ((1-κg)/(2-κg)-ϵ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$( (1 - \kappa ^g)/(2 - \kappa ^g) - \epsilon )$$\end{document}-approximation for the cardinality-constrained BP maximization, where κg\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\kappa ^g$$\end{document} is the curvature of the corresponding supermodular function. Our results improve the previous best approximation bounds.