Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00176 The Multi-Commodity Source Location Problems and the Price of Greed Hiro Ito , Mike Paterson , and Kenya Sugihara Vol. 13, no. 1, pp. 55-73, 2009. Regular paper Abstract Given a graph G=(V,E), we say that a vertex subset S ⊆ V covers a vertex v ∈ V if the edge-connectivity between S and v is at least a given integer k, and also say that S covers an edge vw ∈ E if v and w are both covered. We propose the multi-commodity source location problem, which is such that given a vertex- and edge-weighted graph G, p players each select q vertices, and obtain a profit that is the total over all players of the weight of each player's covered vertices and edges. However, vertices selected by one player cannot be selected by the other players. The goal is to maximize the total profits of all players. We show that the price of greed, which indicates the ratio of the total profit of cooperating players to that of selfish players based on an ordered strategy, is tightly bounded by min{ p,q}. Also when k=2, we obtain tight bounds for vertex-unweighted trees when sources are located on the leaves.
|
Accepted: December 2008. Revised: December 2008. Reviewed: July 2008. Published: February 2009. Revised: August 2008. Final: January 2009. Reviewed: December 2008. Revised: November 2008. Reviewed: November 2008. Submitted: January 2008. Communicated by Md. Saidur Rahman |
| Journal of Graph Algorithms and Applications |