“We study correlation clustering in the streaming setting. This problem has been studied extensively and numerous algorithms have been developed, most requiring multiple passes over the stream. … We present a single-pass algorithm that obtains a 5-approximation using O(n) space. The algorithm itself is extremely simple and has implications beyond the streaming setting (such as for dynamic and local computation algorithms). The approximation analysis, on the other hand, is delicate and in fact tight.”

Read the paper and see the full list of authors in the Society for Industrial and Applied Mathematics.