Supplementary Material: Memory-Efficient Approximation Algorithms for M

Upper bound on the objective. The proof consists of three parts. Upper bound on the objective. Upper bound on outer iteration complexity. Finally, we compute an upper bound on the complexity of each iteration, i.e., inner iteration complexity, of Algorithm 1. Upper bound on inner iteration complexity. We now derive an upper bound on N .