Maintaining Assignments Online: Matching, Scheduling, and Flows

DOI10.1137/1.9781611973402.35zbMath1421.68250OpenAlexW4247656554MaRDI QIDQ5383995

Anupam Gupta, Amit Kumar, Clifford Stein

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973402.35

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Directed graphs (digraphs), tournaments (05C20) Online algorithms; streaming algorithms (68W27) Flows in graphs (05C21)

Related Items (12)

Online maximum matching with recourse ⋮ Simultaneously load balancing for every p-norm, with reassignments ⋮ Online load balancing with general reassignment cost ⋮ Serve or skip: the power of rejection in online bottleneck matching ⋮ On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Online load balancing on uniform machines with limited migration ⋮ Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem ⋮ Unnamed Item ⋮ Online Maximum Matching with Recourse ⋮ Shortest augmenting paths for online matchings on trees ⋮ Permutation Strikes Back: The Power of Recourse in Online Metric Matching ⋮ Shortest Augmenting Paths for Online Matchings on Trees

This page was built for publication: Maintaining Assignments Online: Matching, Scheduling, and Flows