Some concepts of stability analysis in combinatorial optimization

摘要: Abstract This paper surveys the recent results in stability analysis for discrete optimization problems, such as a traveling salesman problem, an assignment shortest path Steiner scheduling problem and so on. The terms “stability”, “sensitivity” or “postoptimal analysis” are generally used phase of algorithm at which solution (or solutions) has been already found, additional calculations also performed order to investigate how this depends on changes data. In paper, main attention is paid region ball optimal approximate solutions. A short sketch some other close added emphasize differences approach surveyed.