@inbook{39f4b67d2fa84c63844a262bbfd127ba,
title = "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.",
author = "Karlis Freivalds",
year = "2003",
doi = "10.1007/3-540-44867-5\_11",
language = "English",
isbn = "3540402055",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "134--147",
editor = "Klaus Jansen and Marian Margraf and Monaldo Mastrolilli and Rolim, \{Jose D. P.\}",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "Germany",
}