Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Online Universal Facility Location
event speaker icon
Israel Shalom (M.Sc. Thesis Seminar)
event date icon
Wednesday, 13.04.2011, 14:00
event location icon
Taub 601
event speaker icon
Advisor: Prof. Joseph (Seffi) Naor
Facility location problems concern assigning requests to servers. The goal is to minimize the total cost which consists of the moving costs and the latency costs. The moving costs depend on the distances between matcheded request/server pairs, while the latency costs depend on the number of requests matched to each server. Facility location problems arise in many natural settings of resource sharing, such as server assignment in cloud computing, network routing and more. Universal Facility Location (UniFL) is the broadest framework for such problems, and it also generalizes load balancing and bipartite matching problems. This talk is about the online version of UniFL, and is based on the work done with and under the supervision of Prof. Seffi Naor. We propose a greedy algorithm and consider various cases based on different latency (congestion) functions. Through somewhat intricate analysis, we find that for many cases the greedy algorithm provides a constant competitive-ratio, and there are some settings in which no algorithm can offer *any* competitive-ratio.