Some concepts of stability analysis in combinatorial optimization

Some concepts of stability analysis in combinatorial optimization

0.00 Avg rating0 Votes
Article ID: iaor19971036
Country: Netherlands
Volume: 58
Issue: 2
Start Page Number: 169
End Page Number: 190
Publication Date: Mar 1995
Journal: Discrete Applied Mathematics
Authors: , ,
Keywords: combinatorial analysis
Abstract:

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

Reviews

Required fields are marked *. Your email address will not be published.