M.Sc Thesis

M.Sc StudentShalom Israel
SubjectOnline Load-Distance Balancing
DepartmentDepartment of Computer Science
Supervisor PROF. Joseph Naor
Full Thesis textFull thesis text - English Version


This work concerns online algorithms, which receive their input sequentially. Decisions made by the online algorithm regarding previous requests are irrevocable. The competitive ratio of an online algorithm is the worst-case ratio between the cost of its output and the cost of the optimum output for the same input.

Particularly, we consider online assignment problems. These concern the assignment of requests to servers, and are relevant to many practical problems; such as sharing computing resources. In the online case, requests arrive one-by-one, and the online algorithm returns the handling server.

Our cost model, Load-Distance Balancing (LDB), is made of two components: one is the distance cost, and the other is the latency cost. The first depends on the distance that is defined between any request/server pair, and the second depends on the latency function of the server as well as the load (number of served requests) on the server.

First, we show that with no further assumptions about latency functions, no online algorithm can guarantee any competitive ratio. We proceed to examining subclasses of latency functions: linear, concave, bounded-slope, polynomial and capacity functions. The last class is particularly useful, since it represents the bipartite matching problem with capacities. In the bipartite matching problem, there are no latencies - the goal is to minimize the total moving cost without exceeding server capacity.

For the first four classes we suggest the greedy algorithm, which makes the locally optimal choice in every step. We find that Greedy (or its variation) is optimal up to a constant in all these subcases. Despite being intuitive, the implementation of Greedy proves difficult, since Greedy has an infinite number of choices to choose from. We solve this problem by creating WaterFill, which acts greedily and works efficiently.

For capacity latencies the analysis is entirely different. We see that the only subcase in which online algorithms can perform well are metric distances, and splittable demands. For this case, we suggest LocalMatch, based on bipartite matching algorithms, and find that it is O(log2k)-competitive. We show a lower bound of Ω(log k) for the competitive ratio of any online algorithm, where k is the number of servers.