Georgia Institute of Technology College of Sciences

Motivated by real-time logistics, I will present a deterministic online algorithm for the Online Minimum Metric Bipartite Matching Problem. In this problem, we are given a set S of server locations and a set R of request locations.The requests arrive one at a time and when it arrives, we must immediately and irrevocably match it to a ``free" server. The cost of matching a server to request is given by the distance between the two locations (which we assume satisfies triangle inequality). The objective of this problem is to come up with a matching of servers to requests which is competitive with respect to the minimum-cost matching of S and R.In this talk, I will show that this new deterministic algorithm performs optimally across different adversaries and metric spaces. In particular, I will show that this algorithm simultaneously achieves optimal performances in two well-known online models -- the adversarial and the random arrival models. Furthermore, the same algorithm also has an exponentially improved performance for the line metric resolving a long standing open question.