TY - GEN
T1 - Online bipartite matching with amortized O(log2 n) replacements
AU - Bernstein, Aaron
AU - Holm, Jacob
AU - Rotenberg, Eva
N1 - Publisher Copyright:
© Copyright 2018 by SIAM.
PY - 2018
Y1 - 2018
N2 - 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(log2 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 any replacement strategy, almost matching the (log n) lower bound. The previous best strategy known achieved amortized O(p n) 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(log2 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(min-Llog2 n, p n log n}) reassignments. We also show that this is close to tight because (min-L, p n}) reassignments can be necessary.
AB - 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(log2 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 any replacement strategy, almost matching the (log n) lower bound. The previous best strategy known achieved amortized O(p n) 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(log2 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(min-Llog2 n, p n log n}) reassignments. We also show that this is close to tight because (min-L, p n}) reassignments can be necessary.
UR - http://www.scopus.com/inward/record.url?scp=85045564975&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85045564975&partnerID=8YFLogxK
U2 - 10.1137/1.9781611975031.61
DO - 10.1137/1.9781611975031.61
M3 - Conference contribution
AN - SCOPUS:85045564975
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 947
EP - 959
BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
A2 - Czumaj, Artur
PB - Association for Computing Machinery
T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Y2 - 7 January 2018 through 10 January 2018
ER -