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(*n*^{1.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*