Technical Report MSC-2013-10

Title: Approximation Algorithms for Soft-Capacitated Connected Facility Location Problems R
Authors: Assaf Rappaport
Supervisors: Danny Raz
Abstract: In recent years, companies such as eBay, Facebook, Google, Microsoft, and Yahoo! have made large investments in massive data centers supporting cloud services. These data centers are becoming the hosting platform for a wide spectrum of composite applications with an increasing trend towards more communication intensive applications. As a result, the bandwidth usage within and between data centers is rapidly growing.

Data centers placement is a challenging set of optimization problems where the goal is to optimally place the applications and their related data over the available infrastructure. Unlike traditional facility location problems, in our case data is continuously updated, and the cost associated with this update increases with the number of data replica and the network distance between them.

We model this problem as a soft-capacitated connected facility location problem, which is NP-Hard in the general case. We present the first deterministic constant approximation algorithm for this problem and show, using extensive simulations and realistic data center and network topology, that our algorithm provides practically good placement decisions.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2013
To the main CS technical reports page

Computer science department, Technion