Geodesic
On the complexity of determining tolerances for $\varepsilon $-optimal solutions to min-max combinatorial optimization problems
Diptesh Ghosh1 ; Gerard Sierksma2
1 Production & Quantitative Methods Area Indian Institute of Management Vastrapur, Ahmedabad 380015, India
2 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.

Voir la notice de l'article provenant de la source Institute of Mathematics Polish Academy of Sciences

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

Diptesh Ghosh 1 ; Gerard Sierksma 2

1 Production & Quantitative Methods Area Indian Institute of Management Vastrapur, Ahmedabad 380015, India
2 Faculty of Economic Sciences University of Groningen P.O. Box 800 9700AV Groningen, The Netherlands 
@article{10_4064_am30_3_5,
     author = {Diptesh Ghosh and Gerard Sierksma},
     title = {On the complexity of determining tolerances
 for $\varepsilon $-optimal solutions to
 min-max combinatorial optimization problems},
     journal = {Applicationes Mathematicae},
     pages = {305--313},
     publisher = {mathdoc},
     volume = {30},
     number = {3},
     year = {2003},
     doi = {10.4064/am30-3-5},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4064/am30-3-5/}
}
TY  - JOUR
AU  - Diptesh Ghosh
AU  - Gerard Sierksma
TI  - On the complexity of determining tolerances
 for $\varepsilon $-optimal solutions to
 min-max combinatorial optimization problems
JO  - Applicationes Mathematicae
PY  - 2003
SP  - 305
EP  - 313
VL  - 30
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4064/am30-3-5/
DO  - 10.4064/am30-3-5
LA  - en
ID  - 10_4064_am30_3_5
ER  - 
%0 Journal Article
%A Diptesh Ghosh
%A Gerard Sierksma
%T On the complexity of determining tolerances
 for $\varepsilon $-optimal solutions to
 min-max combinatorial optimization problems
%J Applicationes Mathematicae
%D 2003
%P 305-313
%V 30
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4064/am30-3-5/
%R 10.4064/am30-3-5
%G en
%F 10_4064_am30_3_5
Diptesh Ghosh; Gerard Sierksma. On the complexity of determining tolerances
 for $\varepsilon $-optimal solutions to
 min-max combinatorial optimization problems. Applicationes Mathematicae, Tome 30 (2003) no. 3, pp. 305-313. doi : 10.4064/am30-3-5. http://geodesic.mathdoc.fr/articles/10.4064/am30-3-5/

Cité par Sources :