A Note on Maximizing Regularized Submodular Functions Under Streaming

The introduced algorithm, which is listed in Algorithm 1, obtains a parameter $\lambda =2$ and starts with an empty set. Algorithm 1 uses sets $S_t$ for certain iterations $t$ from $1$ to $k$ . For some iteration $t$ and part $i$ with $|S_t\cap E_i|<k_i$ , the algorithm greedily selects element $e_t=e_i$ with a maximum distorted marginal gain, that is,

(5) $$e_i\in \arg \underset{e\in E_i}{\max }f(e|S_t)-\lambda \cdot c(e)$$

Algorithm 1 breaks if either all the distorted marginal gains are negative or the iterations reach to $k$ .

The proposed algorithm, which is listed in Algorithm 2, obtains parameters $r=2/3$ ; thus let $\alpha (r)=(2r+1-\sqrt{4r^2+1})/2=2$ , and $h(r)=(1-1/\alpha (r))/$ $(2-1/\alpha (r))=1/3$ . The influence of the distorted marginal gains is intuitively investigated by introducing the above parameter $\alpha (r)$ . Motivated by Ref. [ 37 ], a distorted alternative optimization problem is introduced as follows:

(6) $$T\in \arg \underset{T^{\prime }\in I,T^{\prime }\subseteq E}{\max }h(r)f(T^{\prime })-r\cdot c(T^{\prime })$$

where parameters $r$ and $h(r)$ are stated as before.

Algorithm 2 starts with empty solution $S$ and buffer $B$ . Let $m_t:=h(r)f(e_t)-rc(e_t)$ be a distorted single element value. The lower bound of optimum $O$ estimated by candidate subsets is denoted as $L$ and a set returned by reservoir sampling is denoted as set $R_i$ considering $e_t=e_i$ . For any revealed element $e_t\in E_i$ from $E$ , we construct an increasing geometric progression $\{\tau ={(1+\epsilon )}^j,j\in Z\}$ interval by $m$ is constructed as follows:

(7) $$O_t=\{{(1+\epsilon )}^j:\tau \in [{\displaystyle \frac{\max \{m_t,L\}}{k}},{\displaystyle \frac{\alpha (r)m_t}{r}}]\}$$

For each newly instantiated threshold $\tau \in O_t$ , the algorithm starts with a corresponding candidate solution $S_{\tau }=\mathrm{\varnothing }$ . For each $\tau \in O_t$ , Algorithm 2 updates $S_{\tau }$ with $e_t=e_i\in E_i$ , if the cardinality of $S_{\tau }\cap E_i$ satisfies $|S_{\tau }\cap E_i|<k_i$ and the distorted marginal gain of $e_i$ is larger than threshold $\tau$ , that is,

(8) $$f(e_t|S_{\tau })-\alpha (r)c(e_t)⩾\tau$$

Furthermore, Algorithm 2 updates buffer $B$ if

(9) $$f(e_t|S_{\tau })-\alpha (r)c(e_t)⩾{\displaystyle \frac{L}{k}}$$

and returns the maximal lower bound $L=$ ${\max }_{\tau }f(S_{\tau })-$ $c(S_{\tau })$ . The postprocessing is then followed to obtain good theoretical guarantees.

The postprocessing, which is listed as Algorithm 3, starts with identifying an index ${\tau }^{\prime }$ , such that ${\tau }^{\prime }$ is the smallest $\tau$ if $|S_{\tau }\cap E_i|<k_i$ for each $i$ ; if some part $i$ holds $|S_{\tau }\cap E_i|=k_i$ for each $\tau$ , then the largest $\tau \in O_n$ is denoted by ${\tau }^{\prime }$ . For each $\tau ⩽{\tau }^{\prime }$ , Algorithm 3 relies on the distorted greedy. Distorted greedy, which is listed as Algorithm 1, recalculates the elements in $B$ and $R_i$ , and adds them to $S_{\tau }$ if their marginal gains are nonnegative.

The proposed algorithm, which is listed in Algorithm 2, obtains parameters $r=2/3$ ; thus let $\alpha (r)=(2r+1-\sqrt{4r^2+1})/2=2$ , and $h(r)=(1-1/\alpha (r))/$ $(2-1/\alpha (r))=1/3$ . The influence of the distorted marginal gains is intuitively investigated by introducing the above parameter $\alpha (r)$ . Motivated by Ref. [ 37 ], a distorted alternative optimization problem is introduced as follows:

(6) $$T\in \arg \underset{T^{\prime }\in I,T^{\prime }\subseteq E}{\max }h(r)f(T^{\prime })-r\cdot c(T^{\prime })$$

where parameters $r$ and $h(r)$ are stated as before.

Algorithm 2 starts with empty solution $S$ and buffer $B$ . Let $m_t:=h(r)f(e_t)-rc(e_t)$ be a distorted single element value. The lower bound of optimum $O$ estimated by candidate subsets is denoted as $L$ and a set returned by reservoir sampling is denoted as set $R_i$ considering $e_t=e_i$ . For any revealed element $e_t\in E_i$ from $E$ , we construct an increasing geometric progression $\{\tau ={(1+\epsilon )}^j,j\in Z\}$ interval by $m$ is constructed as follows:

(7) $$O_t=\{{(1+\epsilon )}^j:\tau \in [{\displaystyle \frac{\max \{m_t,L\}}{k}},{\displaystyle \frac{\alpha (r)m_t}{r}}]\}$$

For each newly instantiated threshold $\tau \in O_t$ , the algorithm starts with a corresponding candidate solution $S_{\tau }=\mathrm{\varnothing }$ . For each $\tau \in O_t$ , Algorithm 2 updates $S_{\tau }$ with $e_t=e_i\in E_i$ , if the cardinality of $S_{\tau }\cap E_i$ satisfies $|S_{\tau }\cap E_i|<k_i$ and the distorted marginal gain of $e_i$ is larger than threshold $\tau$ , that is,

(8) $$f(e_t|S_{\tau })-\alpha (r)c(e_t)⩾\tau$$

Furthermore, Algorithm 2 updates buffer $B$ if

(9) $$f(e_t|S_{\tau })-\alpha (r)c(e_t)⩾{\displaystyle \frac{L}{k}}$$

and returns the maximal lower bound $L=$ ${\max }_{\tau }f(S_{\tau })-$ $c(S_{\tau })$ . The postprocessing is then followed to obtain good theoretical guarantees.

The postprocessing, which is listed as Algorithm 3, starts with identifying an index ${\tau }^{\prime }$ , such that ${\tau }^{\prime }$ is the smallest $\tau$ if $|S_{\tau }\cap E_i|<k_i$ for each $i$ ; if some part $i$ holds $|S_{\tau }\cap E_i|=k_i$ for each $\tau$ , then the largest $\tau \in O_n$ is denoted by ${\tau }^{\prime }$ . For each $\tau ⩽{\tau }^{\prime }$ , Algorithm 3 relies on the distorted greedy. Distorted greedy, which is listed as Algorithm 1, recalculates the elements in $B$ and $R_i$ , and adds them to $S_{\tau }$ if their marginal gains are nonnegative.