DIMACS Seminar

Title:

The Primal-Dual Method for Approximation Algorithms

Speaker:

David P. Williamson

IBM Watson

Place:

Room 402, Computer Science Building

Princeton University.

Time:

11:40 AM

Tuesday, April 18, 1995

Abstract:

I will present a generic primal-dual approximation algorithm and its analysis, and show how it implies several classical algorithms (e.g. Dijkstra's shortest path algorithm, Edmonds' minimum-cost arborescence algorithm), some older approximation algorithms (e.g. Bar-Yehuda and Even's algorithm for vertex cover), as well as several recent 2-approximation algorithms for various minimum-cost network design problems, including generalized Steiner trees, T-joins, matching (when edge costs obey the triangle inequality), non-fixed point-to-point connection, and the prize-collecting traveling salesman problem. Repeated applications of the algorithm allows the solution of such problems as the survivable network design problem, in which for given values r_ij, a minimum-cost subgraph must be selected so that there are r_ij edge-disjoint paths between each i,j. The generic nature of the algorithm and theorem makes it easy to derive new algorithms, or give short proofs of known algorithms. Furthermore, experimental results have shown that the algorithm works very well in practice.

This talk is dedicated to the memory of Albert W. Tucker.

Document last modified on February 3, 1995