A primal-dual resource augmentation analysis of a constant approximate algorithm for stable coalitions in a cluster
Nedialko B. Dimitrov, Indrajit Roy · 2008
In this paper we study the following Cluster Profit Problem. Highly parallelizable requests are present on some network nodes. Each request is associated with a tuple (g, r). The requester is willing to pay kg if k machines execute the request in parallel. If some machines work on a request, the machines must pay the request processing cost, r, as well as connection costs to the request. The problem is to find a profit maximizing assignment of machines to requests, such that each machine works on at most one request. The Cluster Profit Problem can be viewed as a profit maximizing variant of the Facility Location Problem. We provide and analyze an algorithm under resource augmentation for the Cluster Profit Problem. Resource augmentation is a technique made famous by the LRU caching analysis. We compare our algorithm with the optimal algorithm operating on a network graph that has a constant factor longer distances. We prove our algorithm is a constant approximation under this resource augmentation. We also show that our algorithm is resilient to group deviations if deviating increases communication costs by a constant factor.