Abstract
Balanced Min and Max Cuts Under the Triangle Inequality
by: Teofilo F. Gonzalez and Toshio Murayama
Abstract:
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 theedges joining vertices in different subsets. We concentrate on the$(k,t)$-Max-Cut and $(k,t)$-Min-Cut problems defined over complete graphs thatsatisfy the triangle inequality as well as on a restricted class of thesegraphs.We establish a bound for the objective function value of an optimal partitionfor the $(k,t)$-Min-Cut and $(k,t)$-Max-Cut problems, and give probleminstances that asymptotically achieve this bound. The existence of this smallbound is important because it implies that any feasible solution is anear-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 wherethe weights change, vertices are added and/or deleted, etc., any feasiblesolution is a reasonably good solution.We also present a characterization of an optimal partition for theone-dimensional version of our partitioning problems, and present a simple $O(n\\log n)$ time algorithm to generate an optimal partition. For some restrictedversions of these problems we present $O(n)$ time algorithms, and for otherversions we establish a robust $\\Omega(n \\log n)$ lower bound for the timerequired to compute an optimal partition.
Keywords:
Approximation Algorithms, Lower Bounds, Clustering, TriangleInequality, Online Algorithms.
Date:
October 1998
Document: 1998-25
