Home | Issues | About JGAA | 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 Multi-Commodity Source Location Problems and the Price of Greed
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.
|
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
|
Journal Supporters
|