A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game

DOI10.1137/050646408zbMath1225.68272OpenAlexW2111072608MaRDI QIDQ3532565

Stefan H. M. Van Zwam, Jochen Könemann, Stefano Leonardi, Guido Schäfer

Publication date: 28 October 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://research.tue.nl/nl/publications/a-groupstrategyproof-cost-sharing-mechanism-for-the-steiner-forest-game(7c82b48b-1938-46ed-b59f-51f754e5d581).html

zbMATH Keywords

approximation algorithmsmechanism designprimal-dual algorithmsgroup-strategyproofnessSteiner forests

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (16)

Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Optimal cost sharing for capacitated facility location games ⋮ When ignorance helps: graphical multicast cost sharing games ⋮ Approximation algorithms for Steiner forest: An experimental study ⋮ Strategic cooperation in cost sharing games ⋮ Unnamed Item ⋮ A Local-Search Algorithm for Steiner Forest ⋮ Stronger MIP formulations for the Steiner forest problem ⋮ Black-box reductions for cost-sharing mechanism design ⋮ An Exact Algorithm for the Steiner Forest Problem ⋮ A partition-based relaxation for Steiner trees ⋮ Approximation of Steiner forest via the bidirected cut relaxation ⋮ A Characterization of Undirected Graphs Admitting Optimal Cost Shares ⋮ Distance Transformation for Network Design Problems ⋮ Efficient Black-Box Reductions for Separable Cost Sharing ⋮ Unnamed Item

This page was built for publication: A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game