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

Volume 30 / 2003

Diptesh Ghosh, Gerard Sierksma Applicationes Mathematicae 30 (2003), 305-313 MSC: Primary 90C31. DOI: 10.4064/am30-3-5


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]).


  • Diptesh GhoshProduction & Quantitative Methods Area
    Indian Institute of Management
    Vastrapur, Ahmedabad 380015, India
  • Gerard SierksmaFaculty of Economic Sciences
    University of Groningen
    P.O. Box 800
    9700AV Groningen, The Netherlands

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image