Replacing spectral techniques for expander ratio, normalized cut and conductance by combinatorial flow algorithms

Mathematics – Optimization and Control

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

The paper was submitted to ArXiv system by author

Scientific paper

Several challenging problem in clustering, partitioning and imaging have traditionally been solved using the "spectral technique". These problems include the normalized cut problem, the graph expander ratio problem, the Cheeger constant problem and the conductance problem. These problems share several common features: all seek a bipartition of a set of elements; the problems are formulated as a form of ratio cut; the formulation as discrete optimization is shown here to be equivalent to a quadratic ratio, sometimes referred to as the Raleigh ratio, on discrete variables and a single sum constraint which we call the balance or orthogonality constraint; when the discrete nature of the variables is disregarded, the continuous relaxation is solved by the spectral method. Indeed the spectral relaxation technique is a dominant method providing an approximate solution to these problems. We propose an algorithm for these problems which involves a relaxation of the orthogonality constraint only. This relaxation is shown here to be solved optimally, and in strongly polynomial time, in O(mn log((n^2) / m) for a graph on $n$ nodes and $m$ edges. The algorithm, using HPF (Hochbaum's Pseudo-Flow) as subroutine, is efficient enough to be used to solve these bi-partitioning problems on millions of elements and more than 300 million edges within less than 10 minutes. It is also demonstrated, via a preliminary experimental study, that the results of the combinatorial algorithm proposed often improve dramatically on the quality of the results of the spectral method.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Replacing spectral techniques for expander ratio, normalized cut and conductance by combinatorial flow algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Replacing spectral techniques for expander ratio, normalized cut and conductance by combinatorial flow algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Replacing spectral techniques for expander ratio, normalized cut and conductance by combinatorial flow algorithms will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-424025

All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.