On the cut-query complexity of approximating max-cut

Orestis Plevrakis, Seyoon Ragavan, S. Matthew Weinberg

We consider the problem of query-efficient global max-cut on a weighted undirected graph in the value oracle model examined by [RSW18]. Graph algorithms in this cut query model and…