The Multi-Commodity Source Location Problems and the Price of Greed - Ito, Hiro; Paterson, Mike; Sugihara, Kenya (Journal of Graph Algorithms and Applications, 2009)
Given a graph G=(V,E), we say that a vertex subsetS ⊆ V covers a vertex v ∈ V if the edge-connectivity between Sand v is at least a given integer k, andalso say that S covers an edge vw ∈ E if vand w are both covered. We propose the multi-commodity source locationproblem, which is such that given a vertex- andedge-weighted graph G, p players each select q vertices, andobtain a profit that is the total over all players of the weight of each player's coveredvertices and edges. However, vertices selected by one player cannotbe selected by the other players. The goal is tomaximize the total profits of all players.We show that the price of greed, which indicates theratio of the total profit of cooperating players to thatof selfish players based on an ordered strategy,is tightly bounded by min{ p,q}. Also whenk=2, we obtain tight bounds for vertex-unweighted treeswhen sources are located on the leaves. <!---->