Online Bipartite Matching with Amortized O(log 2 n) Replacements
Online Bipartite Matching with Amortized O(log 2 n) Replacements
复制标题
DOI：
10.1145/3344999
复制
发表时间：
2017-07
期刊：
影响因子：
--
通讯作者：
A. Bernstein;J. Holm;E. Rotenberg
中科院分区：
文献类型：
--
作者：
A. Bernstein;J. Holm;E. Rotenberg
在带替换的在线二部匹配问题中，给出了二分图一侧的所有顶点，而另一侧的顶点与它们的所有关联边一起逐个到达。目标是保持最大匹配，同时最大限度地减少对匹配的更改(替换)数量。我们证明了贪婪算法(记为SAP协议)每次插入至多使用O(Log2n)个分期替换，其中n是插入的顶点总数。这是第一次对任何替换策略实现多对数替换的分析，几乎匹配Ω(Logn)下界。此前已知的最佳战略实现了O(√n)的分期更换[博塞克、莱尼奥夫斯基、桑科夫斯基、齐奇、FOCS 2014年]。特别是对于SAP协议，除了在特殊情况下，没有什么比平凡的O(N)界更好的。我们的分析立即证明了容量受限分配问题的O(Log2n)重分配的上界是相同的，其中二分图静态边的每个顶点都被初始化为服务于多个顶点的能力。我们还分析了最小化最大服务器负载的问题。我们证明了如果最终图有最大服务器负载L，则SAP协议进行了O(min{L log2n，√nlogn})次分期重新分配。我们还证明了这几乎是紧的，因为Ω(min{L，√n})重新分配是必要的。
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(log 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 any replacement strategy, almost matching the Ω (log n) lower bound. The previous best strategy known achieved amortized O(√ n) replacements [Bosek, Leniowski, Sankowski, Zych, FOCS 2014]. For the SAP protocol in particular, nothing better than the trivial O(n) bound was known except in special cases. Our analysis immediately implies the same upper bound of O(log 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(min { L log2 n , √ nlog n}) reassignments. We also show that this is close to tight, because Ω (min { L, √ n}) reassignments can be necessary.