A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching
A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching
复制标题
一种稳健且最优的最小度量二分匹配在线算法
DOI：
10.4230/lipics.approx-random.2016.18
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Raghvendra
中科院分区：
文献类型：
--
作者：
S. Raghvendra
我们研究在线最低度量双方匹配问题。在此问题中，我们给出了与服务器和请求位置相对应的点集S和R；这里| s | = | r | = n。所有这些位置都是一些度量空间的点，将服务器与请求匹配的成本是由其在此空间中的位置之间的距离给出的。在此问题中，请求点一次到达一个。当请求到达时，我们必须立即且不可撤销地将其与“免费”服务器匹配。处理所有请求后获得的匹配是在线匹配M。M的成本是其边缘成本的总和。任何在线算法的性能是其在线解决方案M与最低成本匹配的成本的最差比率。
我们为此问题提供了确定性的在线算法。我们的算法是第一个同时在众所周知的对抗和随机到达模型中实现最佳性能。对于对抗模型，我们获得了2N-1 + O（1）的竞争比率；众所周知，没有确定性算法比2N-1更好。在随机到达模型中，我们的算法获得了2H_N -1 + O（1）的竞争比率；其中h_n是第n个谐波数。我们还证明，在此模型中，任何在线算法的竞争比率都至少为2H_n -1 -O（1）。
我们使用离线原始偶对偶方法的新变体来计算最低成本匹配以计算在线匹配。我们的原始双重方法基于放松的线性程序。在公制成本下，这种特定的放松有助于我们将在线匹配的成本与离线匹配的成本联系起来，从而导致其强大的属性。
We study the Online Minimum Metric Bipartite Matching Problem. In this problem, we are given point sets S and R which correspond to the server and request locations; here |S|=|R|=n. All these locations are points from some metric space and the cost of matching a server to a request is given by the distance between their locations in this space. In this problem, the request points arrive one at a time. When a request arrives, we must immediately and irrevocably match it to a "free" server. The matching obtained after all the requests are processed is the online matching M. The cost of M is the sum of the cost of its edges. The performance of any online algorithm is the worst-case ratio of the cost of its online solution M to the minimum-cost matching.
We present a deterministic online algorithm for this problem. Our algorithm is the first to simultaneously achieve optimal performances in the well-known adversarial and the random arrival models. For the adversarial model, we obtain a competitive ratio of 2n-1 + o(1); it is known that no deterministic algorithm can do better than 2n-1. In the random arrival model, our algorithm obtains a competitive ratio of 2H_n - 1 + o(1); where H_n is the n-th Harmonic number. We also prove that any online algorithm will have a competitive ratio of at least 2H_n - 1-o(1) in this model.
We use a new variation of the offline primal-dual method for computing minimum cost matching to compute the online matching. Our primal-dual method is based on a relaxed linear-program. Under metric costs, this specific relaxation helps us relate the cost of the online matching with the offline matching leading to its robust properties.