In a recent paper, K\"onemann, Leonardi and Sch\"afer~\cite{KLS05} showed that a natural primal-dual algorithm, \kls, gives rise to a $2$-approximate budget balanced and group-strategyproof cost sharing method for the above game.
In this paper we show that the techniques used in \cite{KLS05} yield a new linear programming relaxation for the Steiner forest problem: the {\em lifted-cut relaxation}. We are able to show that this new undirected relaxation for Steiner forests is strictly stronger than the well-studied {\em undirected cut} relaxation.
Joint work with:
* J. Könemann, University of Waterloo
* S. Leonardi, University of Rome, La Sapienza
* S. van Zwam, Eindhoven University