ABSTRACT
For many practically important optimization problems, no efficient algorithms for solving them exactly or even in an approximate way are known, and, relying on the standard complexity-theoretic assumptions such as P≠NP, it is likely that this situation will never change. To formalize reoptimization setting, first need the notion of a local modification. Intuitively, the additional information that is given in a reoptimization setup seems to be rather powerful. Intriguingly, many reoptimization variants of NP –hard optimization problems are also NP –hard. For many reoptimization problems, algorithms with a constant approximation ratio have been designed, improving over the approximations reachable for computing without additional knowledge. The MinSTP is one of the problems that received most attention in reoptimization. Several different local modifications were considered. Escoffier et al. considered the local modification of adding one or more vertices to the graph that can be either terminals or nonterminals or both.
