Approximation Algorithms for Multicommodity Flow and Normalized Cut Problems: Implementations and Experimental Study

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.