Online maximum matching with recourse
Online maximum matching with recourse
复制标题
DOI：
10.1007/s10878-020-00641-w
复制
发表时间：
2018-01
影响因子：
1
通讯作者：
Spyros Angelopoulos;C. Dürr;Shendan Jin
中科院分区：
文献类型：
--
作者：
Spyros Angelopoulos;C. Dürr;Shendan Jin
我们研究了在线最大匹配问题中的边缘与一个已知的资源parameterk相关联的模型。这个问题的在线算法必须保持一个有效的匹配，而底层图的边一个接一个地呈现。在任何时刻，该算法可以决定将边缘包括到匹配中或将其排除，在限制下，每个边缘最多发生k个这样的动作，其中k通常是一个小常数。Avitabile等人在具有追索权的一般在线打包问题的背景下介绍和研究了这个问题（Inf Process Lett 113（3）：81-86，2013），而Boyar等人研究了特殊情况（第15届算法和数据结构研讨会论文集（WADS），第217-228页，2017）。在本文的第一部分中，我们考虑边到达模型，其中到达的边永远不会从图中消失。在这里，我们首先展示了对Avitabile等人的算法AMP的性能的改进分析，通过利用匹配问题的结构。此外，我们还证明了贪婪算法对每个偶数k的竞争比为3/2，对每个奇数k的竞争比为2.此外，我们提出并分析了改进的贪婪算法，我们称之为L-贪婪，我们表明，对于小值的套件优于算法AMP。在下界方面，我们表明，没有确定性算法优于存在，提高了已知的下界。本文的第二部分是致力于theedge到达/离开模型，这是完全动态的变体在线匹配与追索权。对L-Greedy和AMP的分析在此模型中得以实现，并且对所有偶数给出了一个下界。竞争力的比例是3/2。
We study the online maximum matching problem in a model in which the edges are associated with a known recourse parameterk. An online algorithm for this problem has to maintain a valid matching while edges of the underlying graph are presented one after the other. At any moment the algorithm can decide to include an edge into the matching or to exclude it, under the restriction that at mostksuch actions per edge take place, wherekis typically a small constant. This problem was introduced and studied in the context of general online packing problems with recourse by Avitabile et al. (Inf Process Lett 113(3):81–86, 2013), whereas the special casewas studied by Boyar et al. (Proceedings of the 15th workshop on algorithms and data structures (WADS), pp 217–228, 2017). In the first part of this paper we consider theedge arrivalmodel, in which an arriving edge never disappears from the graph. Here, we first show an improved analysis on the performance of the algorithm AMP of Avitabile et al., by exploiting the structure of the matching problem. In addition, we show that the greedy algorithm has competitive ratio 3/2 for every evenkand ratio 2 for every oddk. Moreover, we present and analyze an improvement of the greedy algorithm which we callL-Greedy, and we show that for small values ofkit outperforms the algorithm AMP. In terms of lower bounds, we show that no deterministic algorithm better thanexists, improving upon the known lower bound of. The second part of the paper is devoted to theedge arrival/departure model, which is the fully dynamic variant of online matching with recourse. The analysis ofL-Greedyand AMP carry through in this model; moreover we show a lower bound offor all even. For, the competitive ratio is 3/2.