Design and Performance of Parallel and Distributed Approximation Algorithms for Maxcut

✍ Scribed by Steven Homer; Marcus Peinado

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 327 KB
• Volume: 46
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1997.1381

✦ Synopsis

We develop and experiment with a new parallel algorithm to approximate the maximum weight cut in a weighted undirected graph. Our implementation starts with the recent (serial) algorithm of Goemans and Williamson for this problem. We consider several different versions of this algorithm, varying the interiorpoint part of the algorithm in order to optimize the parallel efficiency of our method. Our work aims for an efficient, practical formulation of the algorithm with close-to-optimal parallelization. We analyze our parallel algorithm in the LogP model and predict linear speedup for a wide range of the parameters. We have implemented the algorithm using the message passing interface (MPI) and run it on several parallel machines. In particular, we present performance measurements on the IBM SP2, the Connection Machine CM5, and a cluster of workstations. We observe that the measured speedups are predicted well by our analysis in the LogP model. Finally, we test our implementation on several large graphs (up to 13,000 vertices), particularly on large instances of the Ising model.