Approximation Algorithms for Multicommodity Flow and Normalized Cut Problems: Implementations and Experimental Study
thesis
posted on 2004-04-06, 00:00authored byYing Du
The thesis presents the theory, implementation and experimental validation of a fast approximation multicommodity flow algorithm and, as an important application of this multicommodity flow algorithm, the first provably good approximation algorithm for the minimum normalized cut problem. The normalized cut problem has been applied to segment static images. Our experimental results of the implementation of both algorithms show that the output quality of our approach compares favorably against some previous approximation multicommodity flow implementation and the eigenvalue/eigenvector based normalized cut implementation. We also show the comparisons on the execution times and analyze the underlying reasons.
History
Date Created
2004-04-06
Date Modified
2018-10-08
Research Director(s)
Dr. Patrick J. Flynn
Committee Members
Dr. Patrick J. Flynn
Dr. Danny Z. Chen
Dr. Jesus A. Izaguirre
Degree
Master of Science in Computer Science and Engineering