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.

From primal-dual to cost shares and back: a stronger LP relaxation for the Steiner forest problem / Jochen, Koenemann; Leonardi, Stefano; Guido, Schaefer; Stefan Van, Zwam. - 3580:(2005), pp. 930-942. (Intervento presentato al convegno 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005) tenutosi a Lisbon; PORTUGAL) [10.1007/11523468_75].

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

LEONARDI, Stefano;
2005

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.
2005
32nd International Colloquium on Automata, Languages and Programming (ICALP 2005)
Steiner trees; game
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
From primal-dual to cost shares and back: a stronger LP relaxation for the Steiner forest problem / Jochen, Koenemann; Leonardi, Stefano; Guido, Schaefer; Stefan Van, Zwam. - 3580:(2005), pp. 930-942. (Intervento presentato al convegno 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005) tenutosi a Lisbon; PORTUGAL) [10.1007/11523468_75].
File allegati a questo prodotto
File Dimensione Formato  
VE_2005_11573-60060.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 143.93 kB
Formato Adobe PDF
143.93 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/60060
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 11
social impact