On the complexity of determining tolerances for $\varepsilon $-optimal solutions to min-max combinatorial optimization problems

Diptesh Ghosh ¹   ; Gerard Sierksma ²

¹ Production & Quantitative Methods Area Indian Institute of Management Vastrapur, Ahmedabad 380015, India
² Faculty of Economic Sciences University of Groningen P.O. Box 800 9700AV Groningen, The Netherlands

Applicationes Mathematicae, Tome 30 (2003) no. 3, pp. 305-313

Résumé

This paper studies the complexity of sensitivity analysis for optimal and $\varepsilon $-optimal solutions to general 0-1 combinatorial optimization problems with min-max objectives. Van Hoesel and Wagelmans [9] have studied the complexity of sensitivity analysis of optimal and $\varepsilon $-optimal solutions to min-sum problems, and Ramaswamy et al. [17] the complexity of sensitivity analysis of optimal solutions to min-max problems. We show that under some mild assumptions the sensitivity analysis of $\varepsilon $-optimal solutions to min-max problems is easy if and only if the original problem is easy. This result is interesting since it immediately applies to a large number of problems, and also because the technique used to prove it is different from the ones used in the related papers (for example, in [17] and [9]).

Détail

DOI : 10.4064/am30-3-5

Keywords: paper studies complexity sensitivity analysis optimal varepsilon optimal solutions general combinatorial optimization problems min max objectives van hoesel wagelmans have studied complexity sensitivity analysis optimal varepsilon optimal solutions min sum problems ramaswamy complexity sensitivity analysis optimal solutions min max problems under mild assumptions sensitivity analysis varepsilon optimal solutions min max problems easy only original problem easy result interesting since immediately applies large number problems because technique prove different related papers example