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

• Autorzy: Diptesh Ghosh , Gerard Sierksma
• Języki publikacji: EN

Abstrakty

EN

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

Kategorie tematyczne

• 90C31: Sensitivity, stability, parametric optimization

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Applicationes Mathematicae
• Rocznik: 2003
• Tom: 30
• Numer: 3
• Strony: 305-313

Daty

wydano

2003

Twórcy

autor

Diptesh Ghosh

• Production & Quantitative Methods Area, Indian Institute of Management, Vastrapur, Ahmedabad 380015, India

autor

Gerard Sierksma

• Faculty of Economic Sciences, University of Groningen, P.O. Box 800, 9700AV Groningen, The Netherlands

Identyfikatory

DOI

10.4064/am30-3-5