A Nondifferentiable Optimization Approach to Ratio-Cut Partitioning

We propose a new method for finding the minimum ratio-cut of a graph. Ratio-cut is NP-hard problem for which the best previously known algorithm gives an O(log n)-factor approximation by solving its dually related maximum concurrent flow problem. We formulate the minimum ratio-cut as a certain nondifferentiable optimization problem, and show that the global minimum of the optimization problem is equal to the minimum ratio-cut. Moreover, we provide strong symbolic computation based evidence that any strict local minimum gives an approximation by a factor of 2. We also give an efficient heuristic algorithm for finding a local minimum of the proposed optimization problem based on standard nondifferentiable optimization methods and evaluate its performance on several families of graphs. We achieve O(n1.6) experimentally obtained running time on these graphs.


Click on the following title to view and download the paper in PostScript format.

A Nondifferentiable Optimization Approach to Ratio-Cut Partitioning
K. Freivalds, Workshop on Experimental and Efficient Algorithms (WEA 2003), LNCS vol. 2647,  pp. 134–147. Springer-Verlag, 2003.
This version has been shortened to fit space constraints. Click here for the full version.

Return to publications