A Robust and Optimal Algorithm for Online Minimum Metric Bipartite Matching
Algorithm by Dr. Sharath Raghvendra(Assistant Professor, Computer Science, Virginia Tech)
Implementation: Prathyush Sambaturu(Graduate Student, Computer Science, Virginia Tech)
In an era of instant gratification, consumers desire speedy access to goods and services. Several new businesses, therefore, have promised on-demand delivery to consumers. Such ventures have service vehicles across the city to serve any request. For example, Uber has several cabs (or servers) across a city. When a new request arrives, they match one of the available servers to this request. Each such match has an associated cost. For instance, this cost could be the distance/time taken by the server to reach the request location. The objective of these ventures is to minimize the total cost of all the assignments made. A primary difficulty is that when servers are matched to requests, we do not have complete knowledge of all request locations. This makes it impossible to achieve smallest cost solution every time.
This paper presents a new online algorithm for the metric bipartite matching problem mentioned above. This algorithm simultaneously achieves optimal performances in two well-studied online models- the adversarial model and the random arrival model. Our algorithm takes only time to make each assignment. See details in this paper.
We have implemented our algorithm and compared it against the previous best-known algorithm for this problem which was independently discovered by Khuller, Mitchell, Vazirani and Kalyanasundaram and Purhs. The source code is available here.. Our algorithm consistently outperforms previous algorithm. Below, we compare the performances of the two algorithms for the case where requests are generated uniformly random from a unit square with Euclidean costs between locations. In this figure, cost ratio is the ratio of the costs of the online solution to the best possible offline solution. In comparison to previous work, our algorithm gives a 8-10% improvement in cost ratio.
