Minimum cost perfect matching with delays for two sources

DOI10.1016/j.tcs.2018.07.004zbMath1407.68558OpenAlexW2883104186MaRDI QIDQ1628601

Yuval Emek, Yuyi Wang, Yaacov Shapiro

Publication date: 4 December 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.07.004

zbMATH Keywords

competitive analysisonline algorithmsmin-cost perfect matching with delaystwo sources

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Cites Work

• On the advice complexity of online bipartite matching and online stable marriage
• On-line algorithms for weighted bipartite matching and stable marriages
• Bayesian Mechanism Design
• AdWords and generalized online matching
• Randomized online algorithms for minimum metric bipartite matching
• Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays
• Online Weighted Matching
• Min-Cost Bipartite Perfect Matching with Delays
• Paths, Trees, and Flowers
• Online matching: haste makes waste!
• Maximum matching and a polyhedron with 0,1-vertices
• Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Minimum cost perfect matching with delays for two sources