Min-Cost Bipartite Perfect Matching with Delays

DOI10.4230/LIPIcs.APPROX-RANDOM.2017.1zbMath1467.68219OpenAlexW2750046462MaRDI QIDQ5002601

Rahul Makhijani, Itai Ashlagi, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Roger Wattenhofer, Yuyi Wang, Moses Charikar, Yossi Azar

Publication date: 28 July 2021

Full work available at URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.1

zbMATH Keywords

competitive analysisbipartite matchingonline algorithms with delayed service

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (9)

Minimum cost perfect matching with delays for two sources ⋮ Asymptotically Optimal Control of a Centralized Dynamic Matching Market with General Utilities ⋮ Caching with Time Windows and Delays ⋮ Technical Note—Online Hypergraph Matching with Delays ⋮ Unnamed Item ⋮ Deterministic min-cost matching with delays ⋮ Competitive analysis for two variants of online metric matching problem ⋮ Impatient Online Matching ⋮ On the Optimal Design of a Bipartite Matching Queueing System

Cites Work

• Unnamed Item
• On randomization in on-line computation.
• A Polylogarithmic-Competitive Algorithm for the k -Server Problem
• Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays
• On Matching and Thickness in Heterogeneous Dynamic Markets
• A dynamic model of barter exchange
• Algorithms – ESA 2004

This page was built for publication: Min-Cost Bipartite Perfect Matching with Delays