@inproceedings{e95701a509d14ddc9b1e36cc3b37d507,

title = "From primal-dual to cost shares and back : a stronger LP relaxation for the Steiner forest problem",

abstract = "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 [1] 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 [1] which allows for a simpler proof of the budget balancedness of the algorithm from [1]. 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.",

author = "J. K{\"o}nemann and S. Leonardi and G. Sch{\"a}fer and {Zwam, van}, S.H.M.",

year = "2005",

doi = "10.1007/11523468_75",

language = "English",

isbn = "3-540-27580-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "930--942",

editor = "L. Caires and G.F. Italiano and L. Monteiro and C. Palamidessi and M. Yung",

booktitle = "Automata, Languages and Programming (Proceedings 32rd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005)",

address = "Germany",

}