2026-07-22T01:28:54Z https://drops.dagstuhl.de/oai

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

Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line Raghvendra, Sharath Bipartite Matching Online Algorithms Adversarial Model Line Metric In the online metric bipartite matching problem, we are given a set S of server locations in a metric space. Requests arrive one at a time, and on its arrival, we need to immediately and irrevocably match it to a server at a cost which is equal to the distance between these locations. A alpha-competitive algorithm will assign requests to servers so that the total cost is at most alpha times the cost of M_{Opt} where M_{Opt} is the minimum cost matching between S and R. We consider this problem in the adversarial model for the case where S and R are points on a line and |S|=|R|=n. We improve the analysis of the deterministic Robust Matching Algorithm (RM-Algorithm, Nayyar and Raghvendra FOCS'17) from O(log^2 n) to an optimal Theta(log n). Previously, only a randomized algorithm under a weaker oblivious adversary achieved a competitive ratio of O(log n) (Gupta and Lewi, ICALP'12). The well-known Work Function Algorithm (WFA) has a competitive ratio of O(n) and Omega(log n) for this problem. Therefore, WFA cannot achieve an asymptotically better competitive ratio than the RM-Algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sharath Raghvendra 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.67 urn:nbn:de:0030-drops-87803 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.67 eng https://creativecommons.org/licenses/by/3.0/legalcode