The Primal-Dual Schema for Approximation Algorithms: Where Does it Stand, and Where Can it Go?

A large fraction of the theory of approximation algorithms, as we know it today, is built around linear programming. LP offers two fundamental algorithm design techniques: rounding and the primal-dual schema. In the past, the latter technique has yielded the most efficient known algorithms for some cornerstone problems in $P$, including matching, flow and shortest paths. Its adaptation to the setting of approximation algorithms has been equally potent, yielding approximation algorithms with good factors and good running times for a diverse collection of problems, including set cover, Steiner tree, Steiner network, facility location, $k$-median, feedback vertex set and $k$-MST. Besides giving an overview of algorithms for some of these problems, I will discuss the historical milestones in the development of this schema, as well as present reasons for believing that the full potential of this schema has yet to be realized in the setting of approximation algorithms.