This paper studies the complexity of sensitivity analysis for optimal and ε-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 ε-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 ε-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]).
@article{bwmeta1.element.bwnjournal-article-doi-10_4064-am30-3-5,
author = {Diptesh Ghosh and Gerard Sierksma},
title = {On the complexity of determining tolerances for $\epsilon$-optimal solutions to min-max combinatorial optimization problems},
journal = {Applicationes Mathematicae},
volume = {30},
year = {2003},
pages = {305-313},
zbl = {1125.90401},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-am30-3-5}
}
Diptesh Ghosh; Gerard Sierksma. On the complexity of determining tolerances for ε-optimal solutions to min-max combinatorial optimization problems. Applicationes Mathematicae, Tome 30 (2003) pp. 305-313. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-am30-3-5/