The k–server problem is of significant importance to the theoretical computer science and the operations research community. In this problem, we are given k servers, their initial locations and a sequence of n requests that arrive one at a time. All these locations are points from some metric space and the cost of serving a request is given by the distance between the location of the request and the current location of the server selected to process the request. We must immediately process the request by moving a server to the request location. The objective in this problem is to minimize the total distance traveled by the servers to process all the requests. In this thesis, we present an empirical analysis of a new online algorithm for k-server problem. This algorithm maintains two solutions, online solution, and an approximately optimal offline solution. When a request arrives we update the offline solution and use this update to inform the online assignment. This algorithm is motivated by the Robust-Matching Algorithm [RMAlgorithm, Raghvendra, APPROX 2016] for the closely related online bipartite matching problem. We then give a comprehensive experimental analysis of this algorithm and also provide a graphical user interface which can be used to visualize execution instances of the algorithm. We also consider these problems under stochastic setting and implement a lookahead strategy on top of the new online algorithm. / MS / Motivated by real-time logistics, we study the online versions of the well-known bipartite matching and the k-server problems. In this problem, there are servers (delivery vehicles) located in different parts of the city. When a request for delivery is made, we have to immediately assign a delivery vehicle to this request without any knowledge of the future. Making cost-effective assignments, therefore, becomes incredibly challenging. In this thesis, we implement and empirically evaluate a new algorithm for the k-server and online matching problems.

Motivated by problems in logistics, image recognition, and statistics, we consider the server allocation problem. In this problem, we are given $k$ servers (with capacities) and $n$ requests, which are points in a metric space. A server serves a request by moving to the request location, and the goal is to serve all requests while minimizing the total movement of servers, subject to the constraint that the number of requests served by a server cannot exceed its capacity. When the server capacity is $1$, and for the Euclidean metric, the problem reduces to the Euclidean bipartite matching problem. When the capacity is $infty$, suppose we are also provided with the order in which requests are to be served, the problem is the $k$-first come first served routing problem. We also consider a generalization of the $k$-first come first served routing problem to the taxi allocation problem, where each request is associated with a pickup location, dropoff location, and pickup time, and the server's velocity is also given as input. We present new algorithms for the Euclidean bipartite matching problem, showing improvements over existing algorithms. In particular, for two point sets $A, B subset mathbb{R}^d$ with $|A| = |B| = n$ and dimension $d > 1$ being constant, we developed: begin{itemize} item A faster algorithm that computes an $varepsilon$-approximate minimum-cost perfect matching in $O(n(varepsilon^{-O(d^3)}loglog n + varepsilon^{-O(d)}log^4 nlog^5log n))$ time. This is an improvement over previous algorithms, which took $n(varepsilon^{-1}log n)^{Omega(d)}$ time. item An algorithm that boosts the accuracy of any $varepsilon$-additive approximation algorithm, achieving an expected additive error of $min{varepsilon, (dloglog n)w^*}$ from the optimal matching cost $w^*$ in $O(T(n, varepsilon/d)loglog n)$ time, where $T(n, varepsilon)$ is the time complexity of any given $eps$-additive approximation algorithm. end{itemize} For the $k$-first come first served routing problem, we present the following results. begin{itemize} item The online version of the $k$-first come first served routing problem is the celebrated $k$-server problem. The best-known online algorithm for this problem is the Work Function algorithm. We present a new implementation of the work function algorithm, where processing the $i$th request takes $O((i+k)^2)$ time, improving on the previous methods that take $Omega(k(i+k)^2)$ time. item For the offline setting, we show that the $k$-first come first served routing problem and the taxi allocation problem can be reduced to the minimum-cost bipartite matching problem. Using this reduction, begin{itemize} item we develop a time-based divide-and-conquer algorithm to obtain an optimal solution in $tilde{O}(kn^2)$ time, which can be further improved to $tilde{O}(kn)$ when the requests and servers are in two-dimensional Euclidean space, and, item we apply a recently presented geometric divide-and-conquer algorithm to obtain an optimal solution for the taxi routing problem in a two-dimensional Euclidean space. As a result, we obtain significant empirical performance improvements for the taxi allocation problem in a two-dimensional space where the cost of moving from one location to another is lower bounded by the Euclidean cost. end{itemize} end{itemize} / Doctor of Philosophy / In the server allocation problem, we are given n requests and k servers, both as points in a space. A server can serve a request by moving to the request location, and each request can be served by exactly one server. The objective is to optimize the allocation of servers to requests such that the total distance traveled by the servers is minimized. In this thesis, we present efficient algorithms for three specific problems in the server allocation problem framework. First, we consider the case when the servers are restricted to serving up to one request each. This problem reduces to the well-known minimum cost maximum cardinality bipartite matching problem. When the underlying distance is Euclidean, this problem is called the Euclidean bipartite matching problem. We present two efficient algorithms that improve the state-of-the-art for the Euclidean bipartite matching problem. Second, we consider the case when the servers can handle multiple requests. Assuming the requests are given as ordered sequences, a server can serve a subsequence of the request sequence. We devise two efficient algorithms for this problem and show empirical performance improvements on the New York Taxi data set. Third, we consider the scenario when the requests appear in an online fashion such that on the arrival of each request, a server must be allocated to it immediately and irrevocably. This problem is the celebrated k-server problem. The work function algorithm is an online algorithm that solves the k-server problem with the best-known competitive ratio. We present a new, faster implementation of the work function algorithm.