Dynamic maintenance of approximate solutions for the traveling salesman problem

emblematic problems of the combinatorial optimization and of the operational
research. Its approximate solution has been tackled with
various tools: approximate algorithms, reoptimization. All of these
methods are static ones, so it’s interesting to face the problem of a
dynamically evolving input instance with vertices being inserted or
deleted: in such a case the salesperson must be able to change his approximate
solution efficiently, maintaining the solution quality as high
as possible.
In my work, the first deterministic algorithms, partially and fully
dynamic, that maintain efficiently a 2-approximate solution for the
TSP are shown. Moreover, heuristic tecniques are investigated, leading
to very efficient insertions of vertices with a little decrease of the
solution quality under a worst case point of view. These results are
obtained maintaining a minimum spanning tree on the evolving graph,
in the former case, or trying to slightly modifiy the minimum spannig
tree, or the hamiltonian circuit itself, while the perturbations take
place, in the latter case.
Moreover: some considerations are carried out, regarding the topological
evolution of approximate solutions after that insertions and
deletions of vertices occuor. This is interesting in order to understand
how much of a previously computed approximate solution can
be preserved after a modification occours. This knowledge could help
in developing algorithms that build a new solution from the previous
one, without having to recompute it from scratch. An algorithm of
these is also presented, leading to a worst case running time of O(n),
while a bare reconstruction would take n + 1 time.