Nondifferentiable optimization based algorithm for
graph 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.
Nondifferentiable optimization
based
algorithm for graph ratio-cut partitioning
Scientific Papers University of Latvia, vol. 669, pp. 61–79. University
of Latvia, 2004.
Return to publications
Contact:
Karlis.Freivalds@mii.lu.lv