Campus Event Calendar

Event Entry

What and Who

From Primal-Dual to Cost Shares and Back: A Stronger LP Relaxation for the Steiner Forest Problem

Guido Schäfer
Università di Roma, "La Sapienza"
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5  
AG Audience

Date, Time and Location

Friday, 22 April 2005
30 Minutes
46.1 - MPII


We consider a game theoretical variant of the Steiner forest problem. An instance of this game consists of an undirected graph $G=(V,E)$, non-negative costs $c(e)$ for all edges $e$ in $E$, and $k$ players. Each player $i$ has an associated pair of terminals $s_i$ and $t_i$. Consider a forest $F$ in $G$. We say that player $i$ is serviced if $s_i$ and $t_i$ are connected in $F$. Player $i$ derives a private utility $u_i$ for receiving service.

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


Guido Schäfer
--email hidden
passcode not visible
logged in users only

Ingrid Finkler, 04/18/2005 10:04
Guido Schäfer, 04/04/2005 13:08
Guido Schäfer, 04/04/2005 12:16 -- Created document.