A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching
From MaRDI portal
Publication:4636450
DOI10.4230/LIPIcs.APPROX-RANDOM.2016.18zbMath1398.68692OpenAlexW2572141964MaRDI QIDQ4636450
Publication date: 19 April 2018
Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2016/6641/pdf/LIPIcs-APPROX-RANDOM-2016-18.pdf/
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Online algorithms; streaming algorithms (68W27)
Related Items (17)
Online bottleneck semi-matching ⋮ Online minimum matching with uniform metric and random arrivals ⋮ A \(o(n)\)-competitive deterministic algorithm for online matching on a line ⋮ An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals ⋮ Dynamic Relaxations for Online Bipartite Matching ⋮ Algorithms for online car-sharing problem ⋮ Online bottleneck matching on a line ⋮ Online semi-matching problem with two heterogeneous sensors in a metric space ⋮ Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship ⋮ A Modern View on Stability of Approximation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Deterministic min-cost matching with delays ⋮ Competitive analysis for two variants of online metric matching problem ⋮ Greedy metric minimum online matchings with random arrivals ⋮ Unnamed Item ⋮ Stochastic Online Metric Matching
This page was built for publication: A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching