Balanced Min and Max Cuts Under the Triangle Inequality
Teofilo F. Gonzalez, Toshio Murayama · 1969
The balanced {\em k-Min-Cut (k-Max-Cut)} problem consists of partitioning the $n$ vertices of an edge weighted complete (undirected) graph into $k$ equally-sized sets so as to minimize (maximize) the sum of the weights of the edges joining vertices in different subsets. We concentrate on the $(k,t)$-Max-Cut and $(k,t)$-Min-Cut problems defined over complete graphs that satisfy the triangle inequality as well as on a restricted class of these graphs. We establish a bound for the objective function value of an optimal partition for the $(k,t)$-Min-Cut and $(k,t)$-Max-Cut problems, and give problem instances that asymptotically achieve this bound. The existence of this small bound is important because it implies that any feasible solution is a near-optimal approximation to the $(k,t)$-Max-Cut and $(k,t)$-Min-Cut problems, for reasonable values of $k$. This shows that in a dynamic environment where the weights change, vertices are added and/or deleted, etc., any feasible solution is a reasonably good solution. We also present a characterization of an optimal partition for the one-dimensional version of our partitioning problems, and present a simple $O(n \log n)$ time algorithm to generate an optimal partition. For some restricted versions of these problems we present $O(n)$ time algorithms, and for other versions we establish a robust $\Omega(n \log n)$ lower bound for the time required to compute an optimal partition.