论文标题
在线图形问题上摊销追索权的力量
The Power of Amortized Recourse for Online Graph Problems
论文作者
论文摘要
在这项工作中，我们研究了单调和目标目标的在线图形问题。我们提出了一种一般的两倍贪婪算法，该算法引用码尺算法达到$ t $ - 竞争力，而最多产生$ \ frac {w _ {\ text {max}}} \ cdot（t+1）}追索权，其中$ w _ {\ text {max}} $和$ w _ {\ text {min}} $是最大的值和最小的正值，可以分配给总和中的元素。我们进一步表明，通过仔细选择引用算法并调整其详细行为，可以改善三个经典图形问题的一般算法。对于独立集，我们完善对我们的一般算法的分析，并表明可以通过$ \ frac {t} {t-1} $ amortized suckiress来实现$ t $竞争力。为了获得最大的基数匹配，我们将算法的贪婪限制为证明可以通过$ \ frac {（2-t^*）} {（t^* - 1）（3-t^*）}+\ frac {t^* - t^*-1}} $ ther $ tar $ tar^$ tar^* +\ frac {1} {j} \ leq t $用于某些整数$ j $。对于Vertex封面，我们表明我们的算法保证了在多项式时间内的任何有限实例的竞争比率严格小于$ 2 $，而最多损失了$ 3.33 $。我们通过使用最佳解决方案作为参考而无需计算它，在多项式时间内几乎无法破坏$ 2 $ 2 $ 2 $ 2。我们指出，该在线结果可以用作离线近似结果（不违反独特的游戏猜想），以部分改进Monien和Speckenmeyer的建设性算法。
In this work, we study online graph problems with monotone-sum objectives. We propose a general two-fold greedy algorithm that references yardstick algorithms to achieve $t$-competitiveness while incurring at most $\frac{w_{\text{max}}\cdot(t+1)}{\min\{1, w_\text{min}\}\cdot(t-1)}$ amortized recourse, where $w_{\text{max}}$ and $w_{\text{min}}$ are the largest value and the smallest positive value that can be assigned to an element in the sum. We further show that the general algorithm can be improved for three classical graph problems by carefully choosing the referenced algorithm and tuning its detailed behavior. For Independent Set, we refine the analysis of our general algorithm and show that $t$-competitiveness can be achieved with $\frac{t}{t-1}$ amortized recourse. For Maximum Cardinality Matching, we limit our algorithm's greed to show that $t$-competitiveness can be achieved with $\frac{(2-t^*)}{(t^*-1)(3-t^*)}+\frac{t^*-1}{3-t^*}$ amortized recourse, where $t^*$ is the largest number such that $t^*= 1 +\frac{1}{j} \leq t$ for some integer $j$. For Vertex Cover, we show that our algorithm guarantees a competitive ratio strictly smaller than $2$ for any finite instance in polynomial time while incurring at most $3.33$ amortized recourse. We beat the almost unbreakable $2$-approximation in polynomial time by using the optimal solution as the reference without computing it. We remark that this online result can be used as an offline approximation result (without violating the unique games conjecture) to partially improve upon the constructive algorithm of Monien and Speckenmeyer.
