Geodesic
The Multi-Commodity Source Location Problems and the Price of Greed
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Second International Workshop on Algorithms and Computation, WALCOM 2008 , Tome 13 (2009) no. 1, pp. 55-73.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00176
Keywords: Multi-commodity source location problem, Source location problem, Price of greed, k-edge-connected 
@article{JGAA_2009_13_1_a3,
     author = {Hiro Ito and Mike Paterson and Kenya Sugihara},
     title = {The {Multi-Commodity} {Source} {Location} {Problems} and the {Price} of {Greed}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {55--73},
     publisher = {mathdoc},
     volume = {13},
     number = {1},
     year = {2009},
     doi = {10.7155/jgaa.00176},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00176/}
}
TY  - JOUR
AU  - Hiro Ito
AU  - Mike Paterson
AU  - Kenya Sugihara
TI  - The Multi-Commodity Source Location Problems and the Price of Greed
JO  - Journal of Graph Algorithms and Applications
PY  - 2009
SP  - 55
EP  - 73
VL  - 13
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00176/
DO  - 10.7155/jgaa.00176
LA  - en
ID  - JGAA_2009_13_1_a3
ER  - 
%0 Journal Article
%A Hiro Ito
%A Mike Paterson
%A Kenya Sugihara
%T The Multi-Commodity Source Location Problems and the Price of Greed
%J Journal of Graph Algorithms and Applications
%D 2009
%P 55-73
%V 13
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00176/
%R 10.7155/jgaa.00176
%G en
%F JGAA_2009_13_1_a3
Hiro Ito; Mike Paterson; Kenya Sugihara. The Multi-Commodity Source Location Problems and the Price of Greed. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Second International Workshop on Algorithms and
Computation, WALCOM 2008
					, Tome 13 (2009) no. 1, pp. 55-73. doi : 10.7155/jgaa.00176. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00176/

Cité par Sources :