Streaming Max-Cut in General Metrics

Shaofeng H. -C. Jiang, Pan Peng, Haoze Wang

Max-Cut is a fundamental combinatorial optimization problem that has been studied in various computational settings. We initiate the study of its streaming complexity in \emph{gene…