New Reoptimization Techniques applied to Steiner Tree Problem.

Abstract: Given an instance of an optimization problem together with an optimal solution for it, a reoptimization problem asks for a solution for a locally modified input instance. In this paper we develop new reoptimization techniques and apply them to the Steiner Tree Problem. Our techniques significantly improve the previous results and apply to a variety of reoptimization problems. [Copyright &y& Elsevier]