This is reposted from cs.stackexchange. I asked the question more than two weeks ago and got no answers, so I thought to repost here.
I am currently self studying approximation algorithms from The Design of Approximation Algorithms (Williamson and Schmoys; page 50 here), specifically the minimum-degree spanning trees (MDST) problem. Given a graph $G$, we need to find a spanning tree $T$ that minimizes the maximum degree of any vertex in $T$.
I understand that the local search algorithm attempts to look at vertices with degree at least $\Delta(T)-\lceil \log_2(n)\rceil $ and try to improve it, and only stops when one cannot improve any such vertex. I understand that this restriction is done to polynomially bound the run time of the algorithm.
My question is, what approximation ratio can we get if we try to improve any vertex? I understand that we cannot show that it runs in polynomial time, but what approximation ratio would hold? Obviously the $2OPT+\lceil \log_2(n)\rceil$ still holds, but can we improve the ratio by trying all vertices? I tried to read the original paper which had another local search algorithm with cost $OPT+1$, but I am not able to prove that this locally optimal tree for all vertices is also an $OPT+1$ algorithm.