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
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 22 April 2005
13:30
30 Minutes
46.1 - MPII
023
Saarbrücken
Abstract
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
Contact
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.
Guido Schäfer, 04/04/2005 13:08
Guido Schäfer, 04/04/2005 12:16 -- Created document.