|M.Sc Student||Rappaport Assaf|
|Subject||Approximation Algorithms for Soft-Capacitated Connected|
Facility Location Problems
|Department||Department of Computer Science||Supervisor||Professor Dan Raz|
|Full Thesis text|
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.