6533b871fe1ef96bd12d186e

RESEARCH PRODUCT

A Nondifferentiable Optimization Approach to Ratio-Cut Partitioning

Kārlis Freivalds

subject

Minimum k-cutMathematical optimizationOptimization problemSpatial networkCutBinary logarithmSymbolic computationConcurrent flowMathematicsRunning time

description

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.

yearjournalcountryeditionlanguage
2003-01-01
https://doi.org/10.1007/3-540-44867-5_11