Minimum cost perfect matching with delays for two sources

DOI10.1007/978-3-319-57586-5_18zbMATH Open1407.68557OpenAlexW2607151438MaRDI QIDQ5283368FDOQ5283368

Authors Yuval Emek, Yaacov Shapiro, Yuyi Wang

Publication date 21 July 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-57586-5_18

Mathematics Subject Classification ID

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

Recommendations

• Minimum cost perfect matching with delays for two sources
• A match in time saves nine: deterministic online matching with delays
• Online matching: haste makes waste!

Cites work

• scientific article; zbMATH DE number 5764830 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• AdWords and generalized online matching
• Maximum matching and a polyhedron with 0,1-vertices
• On the advice complexity of online bipartite matching and online stable marriage
• On-line algorithms for weighted bipartite matching and stable marriages
• Online Weighted Matching
• Online matching and ad allocation
• Online vertex-weighted bipartite matching and single-bid budgeted allocations
• Paths, Trees, and Flowers
• Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays
• Randomized online algorithms for minimum metric bipartite matching

Cited in

(8)

• Randomized algorithm for MPMD on two sources
• Minimum cost perfect matching with delays for two sources
• Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays
• Impatient Online Matching
• Competitive analysis for two variants of online metric matching problem
• Min-cost bipartite perfect matching with delays
• Capacity-insensitive algorithms for online facility assignment problems on a line
• A match in time saves nine: deterministic online matching with delays

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283368)