SupplementaryMaterial: Memory-Efficient ApproximationAlgorithmsforMAX-K-CUTand CorrelationClustering

Let X? be an optimal solution to(SDP) and let X?FW be an optimalsolutionto(SDP-LSE). The matrixC is a scaled Laplacian and so, the only off-diagonal entries that are nonzero correspond to (i,j) E and have value less than zero. We first bound the outer iteration complexity, i.e., the number of iterations of Algorithm 1 until convergence. Upper bound on outer iteration complexity. Let g(X) be a concave and differentiable function andX? an optimal solution of (k-Cut-LSE).