Online bipartite matching with amortized O(^2 n) replacements

DOI10.1145/3344999MaRDI QIDQ5215466zbMATH OpenOpenAlexFDO

Authors Aaron Bernstein, Jacob Holm, Eva Rotenberg

Publication date 11 February 2020

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.06063

zbMATH Keywords

online algorithmsload balancingbipartite graphsmaximum matchingshortest augmenting path

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one by one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. We show that the greedy algorithm that always takes the shortest augmenting path from the newly inserted vertex (denoted the SAP protocol) uses at most amortized $O(lo{g}^{2}n)$ replacements per insertion, where $n$ is the total number of vertices inserted. This is the first analysis to achieve a polylogarithmic number of replacements for emph{any} replacement strategy, almost matching the $Omega(logn)$ lower bound. The previous best strategy known achieved amortized $O(sqrtn)$ replacements [Bosek, Leniowski, Sankowski, Zych, FOCS 2014]. For the SAP protocol in particular, nothing better than then trivial $O(n)$ bound was known except in special cases. Our analysis immediately implies the same upper bound of $O(lo{g}^{2}n)$ reassignments for the capacitated assignment problem, where each vertex on the static side of the bipartition is initialized with the capacity to serve a number of vertices. We also analyze the problem of minimizing the maximum server load. We show that if the final graph has maximum server load $L$, then the SAP protocol makes amortized $O(minLlo{g}^{2}n,sqrtnlogn)$ reassignments. We also show that this is close to tight because $Omega(minL,sqrtn)$ reassignments can be necessary.

Recommendations

• Online bipartite matching with amortized \(\mathcal O(\log^2 n)\) replacements
• Deferred on-line bipartite matching
• Shortest augmenting paths for online matchings on trees
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs

Cited in

(7)

• Maintaining assignments online: matching, scheduling, and flows
• scientific article; zbMATH DE number 7758339 (Why is no real title available?)
• Online bipartite matching with amortized \(\mathcal O(\log^2 n)\) replacements
• Improved bounds for distributed load balancing
• The power of amortized recourse for online graph problems
• Online load balancing with general reassignment cost
• Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem

This page was built for publication: Online bipartite matching with amortized \(O(\log^2 n)\) replacements

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