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

Diptesh Ghosh, and Gerard Sierksma. "On the complexity of determining tolerances for ε-optimal solutions to min-max combinatorial optimization problems." Applicationes Mathematicae 30.3 (2003): 305-313. <http://eudml.org/doc/279432>.

@article{DipteshGhosh2003,
abstract = {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]).},
author = {Diptesh Ghosh, Gerard Sierksma},
journal = {Applicationes Mathematicae},
keywords = {complexity; sensitivity analysis; min-max; 0-1 combinatorial optimization problems},
language = {eng},
number = {3},
pages = {305-313},
title = {On the complexity of determining tolerances for ε-optimal solutions to min-max combinatorial optimization problems},
url = {http://eudml.org/doc/279432},
volume = {30},
year = {2003},
}

TY - JOUR
AU - Diptesh Ghosh
AU - Gerard Sierksma
TI - On the complexity of determining tolerances for ε-optimal solutions to min-max combinatorial optimization problems
JO - Applicationes Mathematicae
PY - 2003
VL - 30
IS - 3
SP - 305
EP - 313
AB - 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]).
LA - eng
KW - complexity; sensitivity analysis; min-max; 0-1 combinatorial optimization problems
UR - http://eudml.org/doc/279432
ER -