A Primal-Dual Approximation Algorithm for Minimum-Cost $k$-Node Connected Subgraph Problem

algorithms have arisen. Among these is the primal-dual method,
which lead to approximation algorithms for many NP-hard problems.
(See Ch. 4 in ``Appr. Alg. for NP-Hard Problems'', D.S.Hochbaum ed.)
Implementations of several algorithms developed have shown that they
also work well in practice, coming within a few percent of optimal.

In this talk I will illustrate this method on the problem of
finding a min-cost $k$-node connected spanning subgraph.
The algorithm is due to Ravi & Williamson, Algorithmica (1997), 18: 21-43.
The proven approximation ratio is $2(1+1/2+...+1/k)=O(log k)$.
Unlike many other primal-dual based approximation algorithms,
this one does note follow straightforwardly from general methodology.