On the core of the minimum cost Steiner tree game in networks

On the core of the minimum cost Steiner tree game in networks

0.00 Avg rating0 Votes
Article ID: iaor19952260
Country: Switzerland
Volume: 57
Issue: 1
Start Page Number: 233
End Page Number: 249
Publication Date: Jun 1995
Journal: Annals of Operations Research
Authors:
Keywords: Steiner problem
Abstract:

A cost allocation problem arising from the Steiner Tree (ST) problem in networks is analyzed. This cost allocation problem is formulated as a cost cooperative game in characteristic function form, referred to as the ST-game. The class of ST games generalizes the class of minimum cost spanning tree games which were used in the literature to analyze a variety of cost allocation problems. In general, the cost of an ST-game may be empty. We construct an efficient Core Heuristic to compute a ‘good’ lower bound on the maximum fraction of the total cost that can be distributed among users while satisfying the core constraints. Based on the Core Heuristic, we also provide a sufficient condition for a given ST not to be optimal for the linear programming relaxation of an integer programming formulation of the ST problem. The Core Heuristic was implemented and tested on 76 data sets from the literature (Wong’s, Aneja’s and Beasley’s Steiner tree problems). Core points were found for 69 of these cases, and points ‘close’ to the core were computed in the others.

Reviews

Required fields are marked *. Your email address will not be published.