Online Bipartite Perfect Matching With Augmentations
Online Bipartite Perfect Matching With Augmentations
复制标题
在线二分完美匹配与增强
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Henry Lin
中科院分区：
文献类型：
--
作者：
Kamalika Chaudhuri;C. Daskalakis;Robert D. Kleinberg;Henry Lin
本文研究了一个在线二分匹配问题，该问题源于无线通信、内容分发和作业调度等应用场景。在我们的问题中，有一个二分图\(G\)，其顶点集由\(n\)个客户端和\(n\)个服务器组成，该图表示每个客户端能够连接的服务器。虽然一开始图\(G\)的边是未知的，但随着每个客户端的到达并请求与服务器匹配，我们会逐渐了解这个图。每个客户端到达时，会揭示出它能够连接的服务器，而算法的目标是在已到达的客户端和服务器之间维持一个匹配。假设图\(G\)存在完美匹配，使得所有客户端都能与服务器匹配，在线算法的目标是最小化切换成本，即客户端为始终维持匹配而需要切换服务器的总次数。尽管目前尚无已知算法能保证在最坏情况下给出比平凡的\(O(n^2)\)更好的切换成本，但我们证明在三种自然情形下，切换成本可以低得多。在第一个结果中，我们表明对于任意具有完美匹配的图\(G\)，如果客户端以随机顺序到达，那么总切换成本以高概率仅为\(O(n \log n)\)。这个界限是紧的，因为我们给出了一个例子，其期望切换成本为\(\Omega(n \log n)\)。在第二个结果中，我们表明如果每个客户端与\(\Theta(\log n)\)个均匀随机选择的服务器有边相连，那么总切换成本会更低；在这种情况下，以高概率仅为\(O(n)\)，并且我们也有\(\Omega(n / \log n)\)的下界。就每个客户端所需的边数而言，我们的结果是紧的，因为为了以高概率保证图\(G\)存在完美匹配，需要\(\Omega(\log n)\)条边。在最后一个结果中，我们推导出了首个已知的在底层图\(G\)为森林时能给出总成本\(O(n \log n)\)的算法。这是首个与森林情形下现有下界相匹配的结果，该下界表明即使图\(G\)限制为森林，任何在线算法的切换成本都必然为\(\Omega(n \log n)\)。
In this paper, we study an online bipartite matching problem, motivated by applications in wireless communication, content delivery, and job scheduling. In our problem, we have a bipartite graph G between n clients and n servers, which represents the servers to which each client can connect. Although the edges of G are unknown at the start, we learn the graph over time, as each client arrives and requests to be matched to a server. As each client arrives, she reveals the servers to which she can connect, and the goal of the algorithm is to maintain a matching between the clients who have arrived and the servers. Assuming that G has a perfect matching which allows all clients to be matched to servers, the goal of the online algorithm is to minimize the switching cost, the total number of times a client needs to switch servers in order to maintain a matching at all times. Although there are no known algorithms which are guaranteed to yield switching cost better than the trivial O(n
2
) in the worst case, we show that the switching cost can be much lower in three natural settings. In our first result, we show that for any arbitrary graph G with a perfect matching, if the clients arrive in random order, then the total switching cost is only O(n log n) with high probability. This bound is tight, as we show an example where the switching cost is Omega(n log n) in expectation. In our second result, we show that if each client has edges to Theta(log n) uniformly random servers, then the total switching cost is even better; in this case, it is only O(n) with high probability, and we also have a lower bound of Omega(n/log n). In terms of the number of edges needed for each client, our result is tight, since Omega(log n) edges are needed to guarantee a perfect matching in G with high probability. In our last result, we derive the first algorithm known to yield total cost O(n log n), given that the underlying graph G is a forest. This is the first result known to match the existing lower bound for forests, which shows that any online algorithm must have switching cost Omega(n log n), even when G is restricted to be a forest.