We consider a game-theoretical variant of the Steiner forest problem, in which each of k users i strives to connect his terminal pair (s i , t i ) of vertices in an undirected, edge-weighted graph G. In  a natural primal-dual algorithm was shown which achieved a 2-approximate budget balanced cross-monotonic cost sharing method for this game.
We derive a new linear programming relaxation from the techniques of  which allows for a simpler proof of the budget balancedness of the algorithm from . Furthermore we show that this new relaxation is strictly stronger than the well-known undirected cut relaxation for the Steiner forest problem.
We conclude the paper with a negative result, arguing that no cross-monotonic cost sharing method can achieve a budget balance factor of less than 2 for the Steiner tree and Steiner forest games. This shows that the results of [1,2] are essentially tight.
|Titel||Automata, Languages and Programming (Proceedings 32rd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005)|
|Redacteuren||L. Caires, G.F. Italiano, L. Monteiro, C. Palamidessi, M. Yung|
|Plaats van productie||Berlin|
|ISBN van geprinte versie||3-540-27580-0|
|Status||Gepubliceerd - 2005|
|Naam||Lecture Notes in Computer Science|
|ISSN van geprinte versie||0302-9743|