of the algorithms show that in this case at least one of the algorithms should output a solution which is strictly better than $1/2$-optimal. In other words, the outcomes of Algorithms \[alg: discrete meta-Greedy\] and \[alg: Reverse discrete meta-Greedy\] are dependent to one another, and the best performance is achieved when the maximum of the two is considered. This justifies why our main algorithm $\texttt{Meta-Greedy}$ can perform strictly better than each of the Algorithms \[alg: discrete meta-Greedy\] and \[alg: Reverse discrete meta-Greedy\]. Using a coupled analysis of the outcome of Algorithms \[alg: discrete meta-Greedy\] and \[alg: Reverse discrete meta-Greedy\], we can bound the performance of $\texttt{Meta-Greedy}$ for different values of $\beta$ and $\gamma$ (see the proof of Theorem \[thm:meta-greedy\] in the appendix). In particular, we can show that the output of $\texttt{Meta-Greedy}$ is at least $0.53$-optimal. The proof of the following theorem carefully analyzes the interplay between the role of the inner and outer maximization problems in . We emphasize that the proof introduces new techniques applicable to other types of minimax submodular problems.

\[thm:meta-greedy\] Consider the $\texttt{Meta-Greedy}$ algorithm outlined in Algorithm \[alg: main discrete meta-Greedy\]. If the functions $f_i$ are monotone and submodular, then we have $$\label{bound-meta-greedy}
\max \Bigl\{  