Streaming and Massively Parallel Algorithms for Euclidean Max-Cut

Nicolas Menand, Erik Waingarten

Given a set of vectors $X=\{x_1,\dots ,x_n\}\subset {\mathbb{R}}^d$, the Euclidean max-cut problem asks to partition the vectors into two parts so as to maximize the sum of Eucl…