Facility Location Variant

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 by viewing the requests for computation as possible facility locations and the machines as customers.

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 com-pare 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.

You can also view a talk a talk on the Cluster Profit Problem.


Nedialko B. Dimitrov and Indrajit Roy. A Primal-Dual Resource Augmentation Analysis of a Constant Approximate Algorithm for Stable Coalitions in a Cluster. Proceedings of the 20th annual Symposium on Parallelism in Algorithms and Architectures (SPAA08), June, 2008

Nedialko B. Dimitrov and Indrajit Roy. A Competitive, Primal-Dual Algorithm for Stable Coalitions in a Cluster. UT Austin, Technical Report T-07-22, May, 2007

Comments and Questions

Add a comment

Add A Comment

Visual Captcha
Code in the picture:
Your Name(*):

© Copyright 2004-2020 - Ned Dimitrov