Easy to say they're hard, but hard to see they're easy - Toward a categorization of tractable multiobjective combinatorial optimization problems



Multiobjective combinatorial optimization problems are known to be hard problems for two reasons: their decision versions are often NP-complete, and they are often intractable. Apart from this general observation, are there also variants or cases of multiobjective combinatorial optimization problems that are easy and, if so, what causes them to be easy? This article is a first attempt to provide an answer to these two questions. Thereby, a systematic description of reasons for easiness is envisaged rather than a mere collection of special cases. In particular, the borderline of easy and hard multiobjective optimization problems is explored. Copyright © 2016 John Wiley & Sons, Ltd.


Journal of Multi-Criteria Decision Analysis, Vol. 24, pp. 82-88, September 2017


Cited by

No citations found