Premium
Easy to say they are Hard, but Hard to see they are Easy— Towards a Categorization of Tractable Multiobjective Combinatorial Optimization Problems
Author(s) -
Figueira José Rui,
Fonseca Carlos M.,
Halffmann Pascal,
Klamroth Kathrin,
Paquete Luís,
Ruzika Stefan,
Schulze Britta,
Stiglmayr Michael,
Willems David
Publication year - 2016
Publication title -
journal of multi‐criteria decision analysis
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.462
H-Index - 47
eISSN - 1099-1360
pISSN - 1057-9214
DOI - 10.1002/mcda.1574
Subject(s) - categorization , combinatorial optimization , computer science , multi objective optimization , optimization problem , mathematical optimization , management science , artificial intelligence , mathematics , machine learning , algorithm , engineering
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.