论文标题
与顶点能力的有限度图中的在线匹配的紧密界限
Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities
论文作者
论文摘要
我们研究了两分图中的$ b $匹配问题$ g =（s，r，e）$。 S $中的每个顶点$ s \是一个具有个人容量$ b_s $的服务器。 R $中的顶点$ r \是在线到达的请求，必须立即分配给合格的服务器。目标是最大化构造匹配的大小。我们假设$ g $是$（k，d）$ - graph〜 \ cite {nw}，其中$ k $指定每个服务器程度上的下限，而$ d $是每个请求程度上的上限。此设置模型匹配及时应用程序中的问题。 我们介绍了确定性在线算法的性能的紧密上限和下限。特别是，我们通过原始的偶尔分析开发了一种新的在线算法。随着服务器容量的增加，最佳竞争比率倾向于〜1，对于任意$ k \ geq d $。因此，几乎可以在线计算几乎最佳的解决方案。我们的结果也适用于顶点加权问题的扩展，因此，每个投标人都会发出同样有价值的投标的AdWords和Auctions问题。 我们的界限提高了以前的最佳竞争比率。对于$ 1-1/e^{k/d} $的渐近竞争力，对于$ k/d \ geq 1 $很小的有趣范围而言，这是一个显着的改善。回想一下$ 1-1/e \约0.63 $。接近〜1的竞争比率的匹配问题很少。先前的结果依赖于随机化或概率输入模型。
We study the $b$-matching problem in bipartite graphs $G=(S,R,E)$. Each vertex $s\in S$ is a server with individual capacity $b_s$. The vertices $r\in R$ are requests that arrive online and must be assigned instantly to an eligible server. The goal is to maximize the size of the constructed matching. We assume that $G$ is a $(k,d)$-graph~\cite{NW}, where $k$ specifies a lower bound on the degree of each server and $d$ is an upper bound on the degree of each request. This setting models matching problems in timely applications. We present tight upper and lower bounds on the performance of deterministic online algorithms. In particular, we develop a new online algorithm via a primal-dual analysis. The optimal competitive ratio tends to~1, for arbitrary $k\geq d$, as the server capacities increase. Hence, nearly optimal solutions can be computed online. Our results also hold for the vertex-weighted problem extension, and thus for AdWords and auction problems in which each bidder issues individual, equally valued bids. Our bounds improve the previous best competitive ratios. The asymptotic competitiveness of~1 is a significant improvement over the previous factor of $1-1/e^{k/d}$, for the interesting range where $k/d\geq 1$ is small. Recall that $1-1/e\approx 0.63$. Matching problems that admit a competitive ratio arbitrarily close to~1 are rare. Prior results rely on randomization or probabilistic input models.
