Friday, December 2, 2005
1:30 p.m. Posner Hall 152
Bill Cunningham
Professor, Department of of Combinatorics & Optimization
University of Waterloo
3-Terminal Cuts and Linear Programming
Given an undirected graph having non-negative weights on the edges, and three specified terminal nodes, the optimal 3-cut problem is to find a minimum weight set of edges whose deletion disconnects the terminals from each other. The corresponding problem with only two terminals is well known to be efficiently solvable, but this problem is hard to solve, even to solve approximately.
I will outline some background on the 3-cut problem, and will describe an attractive geometric relaxation introduced by Calinescu, Karloff, and Rabani, which they used to derive an approximation of provable accuracy. Then I will explain an approach leading to a tight bound on the accuracy of their relaxation, and to an approximation algorithm having a better performance guarantee.
I will emphasize the role of linear programming, both in the solution of the relaxation, and in its analysis.
This talk is based on joint work with Kevin Cheung and Lawrence Tang.
