The Primal-Dual Method for Approximation Algorithms
- David P. Williamson
- IBM Watson
- Room 402, Computer Science Building
- Princeton University.
- 11:40 AM
- Tuesday, April 18, 1995
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