Home  Issues  Aims and Scope  Instructions for Authors 
Special Issue on Selected Papers from the Second International Workshop on Algorithms and
Computation, WALCOM 2008
DOI: 10.7155/jgaa.00176
The MultiCommodity Source Location Problems and the Price of Greed
Vol. 13, no. 1, pp. 5573, 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 edgeconnectivity 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 multicommodity source location
problem, which is such that given a vertex and
edgeweighted 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 vertexunweighted trees
when sources are located on the leaves.

Submitted: January 2008.
Reviewed: July 2008.
Revised: August 2008.
Reviewed: November 2008.
Revised: November 2008.
Reviewed: December 2008.
Revised: December 2008.
Accepted: December 2008.
Final: January 2009.
Published: February 2009.
Communicated by
Md. Saidur Rahman
