论文标题
通过局部改进找到最小跨越树木
Finding minimum spanning trees via local improvements
论文作者
论文摘要
我们考虑了最小重量跨越树的本地搜索算法系列，并由参数$ρ$索引。本地搜索的一个步骤对应于更换当前候选图的连接感应子图，其总重量最多为$ρ$，由同一顶点集的最小跨越树（MST）。修复一个非负随机变量$ x $，并在完整的图表上考虑此本地搜索问题$ k_n $，具有独立的$ x $分布式边缘权重。在$ x $的分布条件下，我们确定一个阈值$ρ^*$，以使以下内容保持。如果启动图（“初始候选MST”）独立于边缘权重，则如果$ρ>ρ^*$本地搜索可以以高概率构建MST（趋于$ 1 $ as $ n \ to \ infty $），而如果$ρ<ρ^*$，则无法具有很高的可能性。
We consider a family of local search algorithms for the minimum-weight spanning tree, indexed by a parameter $ρ$. One step of the local search corresponds to replacing a connected induced subgraph of the current candidate graph whose total weight is at most $ρ$ by the minimum spanning tree (MST) on the same vertex set. Fix a non-negative random variable $X$, and consider this local search problem on the complete graph $K_n$ with independent $X$-distributed edge weights. Under rather weak conditions on the distribution of $X$, we determine a threshold value $ρ^*$ such that the following holds. If the starting graph (the "initial candidate MST") is independent of the edge weights, then if $ρ> ρ^*$ local search can construct the MST with high probability (tending to $1$ as $n \to \infty$), whereas if $ρ< ρ^*$ it cannot with high probability.
