Premium
A note on Steiner tree games
Author(s) -
SkorinKapov Darko,
SkorinKapov Jadranka
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20436
Subject(s) - steiner tree problem , tree (set theory) , mathematical optimization , cost allocation , computer science , function (biology) , core (optical fiber) , dual (grammatical number) , mathematics , combinatorics , economics , art , telecommunications , accounting , literature , evolutionary biology , biology
We investigate the cost allocation strategy associated with the problem of providing some service of common interest from some source to a number of network users, via the minimum cost directed Steiner tree (ST) network that spans the source and all the receivers. The cost of such ST is distributed among its receivers who may be individuals or organizations with possibly conflicting interests. The objective of this article is to develop a reasonably fair and efficient cost allocation scheme associated with the above cost allocation problem. Since finding the optimal Steiner tree is an NP‐hard problem, the input to our cost allocation problem is the best known Steiner tree obtained using some heuristic. To allocate the cost of this Steiner tree to the users (receiver nodes), we formulate the associated Modified Steiner Tree Network (MSTN) game in characteristic function form. Then we construct a primal‐dual cost allocation algorithm which finds some points in the core of the MSTN game and thus results in subsidy‐free cost allocations. Moreover, for the given Steiner tree, our cost allocation scheme is efficient and finds the above “fair” cost allocations in polynomial time. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012