论文标题
预算跨越树问题的单位扰动
Unit Perturbations in Budgeted Spanning Tree Problems
论文作者
论文摘要
图形的最小跨越树是一个经过充分研究的结构，是无数图理论和优化问题的基础。我们研究最小跨越树（MST）扰动问题，目标是花费固定的预算来增加边缘的重量，以便尽可能增加MST的重量。两种流行的扰动模型是散装且连续的。在批量模型中，任何边缘的重量都可以精确增加一次预定的重量。在连续模型中，可以支付分数的成本，以增加任何边缘的重量。弗雷德里克森（Frederickson）和solis-oba \ cite {fs96}已经研究了这两个模型，并表明MST的批量扰动与$ k $ - 切割问题一样困难，而连续的扰动模型可以在poly时溶解。在本文中，我们研究了此问题的中间单元扰动变化，在该变化中，每个边缘的重量可以增加次数，但每次都可以增加整体单位量。我们在多项式时间内提供$（OPT/2 -1）$ - $ opt $是重量的最佳增加。我们还研究了问题的相关双重目标版本，在该目标是将MST的重量增加目标量的同时，同时最大程度地减少扰动成本。我们为此变体提供了$ 2 $ - 附件。此外，我们表明，假设较小的扩展假设，这两个问题都难以近似。我们还指出了Frederickson和Solis-Oba在\ Cite {FS96}方面提供的证据中的错误，以解决连续扰动模型的解决方案。尽管它们的算法是正确的，但它们的分析是有缺陷的。我们在这里提供正确的证明。
The minimum spanning tree of a graph is a well-studied structure that is the basis of countless graph theoretic and optimization problem. We study the minimum spanning tree (MST) perturbation problem where the goal is to spend a fixed budget to increase the weight of edges in order to increase the weight of the MST as much as possible. Two popular models of perturbation are bulk and continuous. In the bulk model, the weight of any edge can be increased exactly once to some predetermined weight. In the continuous model, one can pay a fractional amount of cost to increase the weight of any edge by a proportional amount. Frederickson and Solis-Oba \cite{FS96} have studied these two models and showed that bulk perturbation for MST is as hard as the $k$-cut problem while the continuous perturbation model is solvable in poly-time. In this paper, we study an intermediate unit perturbation variation of this problem where the weight of each edge can be increased many times but at an integral unit amount every time. We provide an $(opt/2 -1)$-approximation in polynomial time where $opt$ is the optimal increase in the weight. We also study the associated dual targeted version of the problem where the goal is to increase the weight of the MST by a target amount while minimizing the cost of perturbation. We provide a $2$-approximation for this variation. Furthermore we show that assuming the Small Set Expansion Hypothesis, both problems are hard to approximate. We also point out an error in the proof provided by Frederickson and Solis-Oba in \cite{FS96} with regard to their solution to the continuous perturbation model. Although their algorithm is correct, their analysis is flawed. We provide a correct proof here.
