An Improved Approximation Algorithm for MULTIWAY CUT

✍ Scribed by Gruia Călinescu; Howard Karloff; Yuval Rabani

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 132 KB
• Volume: 60
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1999.1687

✦ Synopsis

Given an undirected graph with edge costs and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest. Multiway Cut is the problem of finding a multiway cut of minimum cost. Previously, a very simple combinatorial algorithm due to Dahlhaus, Johnson, Papadimitriou, Seymour, and Yannakakis gave a performance guarantee of 2(1& 1 k ). In this paper, we present a new linear programming relaxation for Multiway Cut and a new approximation algorithm based on it. The algorithm breaks the threshold of 2 for approximating Multiway Cut, achieving a performance ratio of at most 1.5& 1 k . This improves the previous result for every value of k. In particular, for k=3 we get a ratio of 7 6 < 4 3 .

2000 Academic Press

1. Introduction

We consider the problem Multiway Cut: Given an undirected graph with nonnegative edge costs and a set of k specified nodes in the graph (called terminals), find a cheapest multiway cut, i.e., subset of the edges whose removal disconnects each terminal from the rest. This is one of several generalizations of the classical undirected s-t cut problem, and it has applications in parallel and distributed computing [24], as well as in chip design.