The minimum cost bipartite matching problem is a well-studied optimization problem in computer science and operations research, with wide-ranging applications in fields such as machine learning, economics, transportation, logistics and biology. A special instance of this problem is the computation of the p-Wasserstein distance which we define next. Given a complete bipartite graph with two disjoint sets of n points in d-dimensional Euclidean space and an integer p ≥ 1, let the cost of an edge be the p-th power of the Euclidean distance between its endpoints. The objective of this problem is to find a minimum-cost matching in this complete bipartite graph. The Hungarian algorithm is a classical method that solves this problem in O(n^3) time. There are many algorithms that have a run time better than that of the Hungarian algorithm if the graphs have non-negative integer edge costs bounded by C. Since the input points have real-valued coordinates and the Euclidean distances can be irrational, such algorithms only return an approximate matching. Thus, the Hungarian algorithm remains the fastest known algorithm to compute an exact matching. In this thesis, we implement a new algorithm in the divide and conquer framework that computes the exact p-Wasserstein distance and has a run time asymptotically better than the Hungarian algorithm for stochastic point sets. Inspired by the techniques used in the algorithm, we also design an alternate version of the Hungarian algorithm that uses a grid- based approach. Our experimental analysis shows that both of our algorithms significantly outperform the classical Hungarian algorithm. / Master of Science / Suppose we have two sets of equal number of items and a list of compatible pairs of items, where a pair is considered compatible if its items belong to different sets. A perfect matching is a subset of compatible pairs where each item is paired with exactly one other item. When trying to find a perfect matching, there may be multiple options, and minimizing the cost of the perfect matching is often desired. This is referred to as the minimum cost bipartite matching problem, which is extensively studied due to its importance in algorithmic theory and operations research. A special instance of this problem is the calculation of the p- Wasserstein distance. It has many practical applications in fields such as machine learning, economics, transportation, logistics and biology. The Hungarian algorithm is the only known algorithm that can compute the exact p-Wasserstein distance. Therefore, our focus is to develop exact algorithms for this problem that perform better than the Hungarian algorithm and can scale efficiently to large datasets.

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.