论文标题
与取消成本进行在线匹配
Online Matching with Cancellation Costs
论文作者
论文摘要
由云计算现货市场中的应用程序和在流行网站上销售横幅广告的激励，我们研究了在线资源分配问题，并通过超预订和取消成本（也称为\ emph {Reakeback}设置。为了模拟这个问题，我们考虑了经典的边缘加权在线匹配问题的变化，决策者可以在其中收回预先分配给较早在线顶点的离线资源的任何部分；但是，通过这样做，决策者不仅失去了先前分配的边缘重量，还必须支付该边缘权重的非负恒定因子$ f $作为额外的罚款。通过回购因子$ f $参数化问题，我们的主要结果是通过一种新颖的原始算法系列的算法获得\ emph {所有可能的值}的最佳竞争算法。我们通过为每个小型和大回购因子制度中的每个小算法获得单独的下限来确定结果的最佳性，并显示我们的原始偶偶算法如何通过适当调整参数作为$ f $的函数来与该下部界限完全匹配。有趣的是，我们的结果显示了一个阶段过渡：对于小的回购制度（$ f <\ frac {e-2} {2} $），最佳竞争比为$ \ frac {e} {e-（1+f）} $ $ -W _ { - 1} \ left（\ frac {-1} {e（1+f）} \ right）$，其中$ w _ { - 1} $是兰伯特W功能的非主要分支。我们使用我们的统一框架进一步研究了该模型变体中的最佳竞争比率，例如与确定性积分分配或具有不同需求的单资源匹配。对于确定性的积分匹配，我们的结果再次显示了一个相位过渡：对于小回购制度（$ f <\ frac {1} {3} $），最佳竞争比为$ \ frac {2} {1-f} $ $ 1+2f+2 \ sqrt {f（1+f）} $。
Motivated by applications in cloud computing spot markets and selling banner ads on popular websites, we study the online resource allocation problem with overbooking and cancellation costs, also known as the \emph{buyback} setting. To model this problem, we consider a variation of the classic edge-weighted online matching problem in which the decision maker can reclaim any fraction of an offline resource that is pre-allocated to an earlier online vertex; however, by doing so not only the decision maker loses the previously allocated edge-weight, it also has to pay a non-negative constant factor $f$ of this edge-weight as an extra penalty. Parameterizing the problem by the buyback factor $f$, our main result is obtaining optimal competitive algorithms for \emph{all possible values} of $f$ through a novel primal-dual family of algorithms. We establish the optimality of our results by obtaining separate lower bounds for each of small and large buyback factor regimes and showing how our primal-dual algorithm exactly matches this lower bound by appropriately tuning a parameter as a function of $f$. Interestingly, our result shows a phase transition: for small buyback regime ($f<\frac{e-2}{2}$), the optimal competitive ratio is $\frac{e}{e-(1+f)}$, and for the large buyback regime ($f\geq \frac{e-2}{2}$), the competitive ratio is $-W_{-1}\left(\frac{-1}{e(1+f)}\right)$, where $W_{-1}$ is the non-principal branch of the Lambert W function. We further study the optimal competitive ratio in variants of this model using our unifying framework, such as matching with deterministic integral allocations or single-resource with different demands. For deterministic integral matching, our results again show a phase transition: for small buyback regime ($f<\frac{1}{3}$), the optimal competitive ratio is $\frac{2}{1-f}$, and for the large buyback regime ($f\geq \frac{1}{3}$), it is $1+2f+2\sqrt{f(1+f)}$.
