2026-07-22T01:29:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6641 2024-03-06T10:38:34Z ddc:004 open_access

A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching Raghvendra, Sharath Online Algorithms Metric Bipartite Matching 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sharath Raghvendra 2016 Is Part Of LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2016.18 urn:nbn:de:0030-drops-66410 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.18 eng https://creativecommons.org/licenses/by/3.0/legalcode