A Nondifferentiable Optimization
Approach to Ratio-Cut Partitioning
Abstract
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.
Download
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
Contact:
Karlis.Freivalds@mii.lu.lv