ABSTRACT
This chapter introduces the key issues in sensitivity analysis and aims to discuss general-purpose techniques for sensitivity analysis. It explores selected results on sensitivity analysis of polynomially-solvable problems and explains the sensitivity analysis of NP-hard problems. The chapter provides an overview of the main algorithmic ideas in sensitivity analysis for combinatorial optimization. Research in sensitivity analysis started shortly after the development of the simple method. A number of sensitivity analysis algorithms are known for polynomially-solvable problems. N. G. Hall and M. E. Posner have shown that, for a large class of NP-hard scheduling problems, performing sensitivity analysis relative to the processing times is itself NP-hard. Hall and Posner study the behavior of greedy heuristics for two NP-hard problems: scheduling two machines to minimize the weighted completion time and scheduling two machines to minimize the makespan.
