Minimum cost perfect matching with delays for two sources

DOI10.1016/J.TCS.2018.07.004MaRDI QIDQ1628601zbMATH OpenOpenAlexWikidataFDO

Authors Yuval Emek, Yaacov Shapiro, Yuyi Wang

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

online algorithmscompetitive analysismin-cost perfect matching with delaystwo sources

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
• Min-cost bipartite perfect matching with delays
• Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays
• The minimum cost perfect matching problem with conflict pair constraints
• Two improved formulations for the minimum latency problem
• On the minimum delay problem
• A Fast Lower Bound for the Minimum Cost Perfect 2-Matching Linear Program
• scientific article; zbMATH DE number 4133845

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
• Min-cost bipartite perfect matching with delays
• 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 matching: haste makes waste!
• 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
• Randomized primal-dual analysis of RANKING for online bipartite matching

Cited in

(4)

• Quick or cheap? Breaking points in dynamic markets
• Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays
• Minimum cost perfect matching with delays for two sources
• Min-cost bipartite perfect 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 Q1628601)