New reoptimization techniques applied to steiner tree problem

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. © 2011 Elsevier B.V.