A parallel min-cut algorithm using iteratively reweighted least squares targeting at problems with floating-point edge weights

作者：Zhu Yao^*; Gleich David F

来源：Parallel Computing, 2016, 59: 43-59.

DOI：10.1016/j.parco.2016.02.003

• Undirected graphs
• s-t min-cut
• Iteratively reweighted least squares
• Laplacian systems
• Parallel linear system solvers

We present a parallel algorithm for the undirected s-t min-cut problem with floating-point valued edge weights. Our overarching algorithm uses an iteratively reweighted least squares framework. Specifically, this algorithm generates a sequence of Laplacian linear systems, which are solved in parallel. The iterative nature of our algorithm enables us to trade off solution quality for execution time, which is distinguished from those purely combinatorial algorithms that only produce solutions at optimum. We also propose a novel two-level rounding procedure that helps to enhance the quality of the approximate min cut solution output by our algorithm. Our overall implementation, including the rounding procedure, demonstrates significant speed improvement over a state-of-the-art serial solver, where it could be up to 200 times faster on commodity platforms.

• 出版日期2016-11