Maintaining Perfect Matchings at Low Cost
Maintaining Perfect Matchings at Low Cost
复制标题
以低成本维持完美匹配
DOI：
10.4230/lipics.icalp.2019.82
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
José Verschae
中科院分区：
文献类型：
--
作者：
J. Matuschke;Ulrike Schmidt;José Verschae
最小成本匹配问题对输入的微小变化非常敏感。即使在一个简单的设置中，例如，当成本来自于线上的度量时，在输入中添加两个节点可能会完全改变最优解。另一方面，人们期望输入的微小变化只会引起构造解的微小变化，以修改边的数量来衡量。我们引入了一个两阶段模型，在这个模型中我们研究了解决方案的质量和鲁棒性之间的权衡。在第一阶段，我们在度量空间中给定一组节点，我们必须计算一个完美的匹配。在第二阶段$2k$出现新节点，我们必须使解决方案与新实例完美匹配。
如果在两个阶段构建的解相对于最小代价完美匹配是$\alpha$ -近似，并且从第一阶段匹配中删除的边的数量最多为$\beta k$，则我们说算法是$(\alpha,\beta)$ -鲁棒的。因此，$\alpha$衡量算法的质量，$\beta$衡量算法的鲁棒性。在这种情况下，我们的目标是通过推导常数$\alpha$和$\beta$的算法来平衡这两个度量。我们证明了存在一种算法，如果提前知道到达节点的数量$2k$，则该算法对任何度量都是$(3,1)$ -鲁棒的。对于$k$未知的情况，情况要复杂得多。我们研究了在线度量下的这种设置，并设计了一个$(10,2)$ -鲁棒算法，该算法构建了一个具有递归结构的解决方案，该算法可以仔细平衡成本和冗余。
The min-cost matching problem suffers from being very sensitive to small changes of the input. Even in a simple setting, e.g., when the costs come from the metric on the line, adding two nodes to the input might change the optimal solution completely. On the other hand, one expects that small changes in the input should incur only small changes on the constructed solutions, measured as the number of modified edges. We introduce a two-stage model where we study the trade-off between quality and robustness of solutions. In the first stage we are given a set of nodes in a metric space and we must compute a perfect matching. In the second stage $2k$ new nodes appear and we must adapt the solution to a perfect matching for the new instance.
We say that an algorithm is $(\alpha,\beta)$-robust if the solutions constructed in both stages are $\alpha$-approximate with respect to min-cost perfect matchings, and if the number of edges deleted from the first stage matching is at most $\beta k$. Hence, $\alpha$ measures the quality of the algorithm and $\beta$ its robustness. In this setting we aim to balance both measures by deriving algorithms for constant $\alpha$ and $\beta$. We show that there exists an algorithm that is $(3,1)$-robust for any metric if one knows the number $2k$ of arriving nodes in advance. For the case that $k$ is unknown the situation is significantly more involved. We study this setting under the metric on the line and devise a $(10,2)$-robust algorithm that constructs a solution with a recursive structure that carefully balances cost and redundancy.
在线 MST 和 TSP 的追索权
DOI：
10.1137/130917703
发表时间：
--
期刊：
SIAM J. Comput.
影响因子：
--
作者：
N. Megow;M. Skutella;J. Verschae;A. Wiese.
通讯作者：
A. Wiese.