The Taub Faculty of Computer Science Events and Talks

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.