Easy to say they are Hard, but Hard to see they are Easy— Towards a Categorization of Tractable Multiobjective Combinatorial Optimization Problems
Easy to say they are Hard, but Hard to see they are Easy— Towards a Categorization of Tractable Multiobjective Combinatorial Optimization Problems
复制标题
说它们很困难很容易，但很难看出它们很简单â 可处理的多目标组合优化问题的分类
DOI：
10.1002/mcda.1574
复制
发表时间：
2017
影响因子：
2
通讯作者：
David Willems
中科院分区：
文献类型：
--
作者：
José Rui Figueira;Carlos M. Fonseca;Pascal Halffmann;Kathrin Klamroth;Luís Paquete;Stefan Ruzika;Britta Schulze;Michael Stiglmayr;David Willems
由于两个原因，多目标组合优化问题被认为是困难的问题：它们的决策版本通常是NP完全的，并且它们通常是难以处理的。除了这种普遍的观察之外，是否也存在容易的多目标组合优化问题的变体或情况，如果存在，是什么导致它们容易？本文是为这两个问题提供答案的第一次尝试。因此，设想对易性的原因进行系统的描述，而不是仅仅收集特殊情况。特别探讨了易、难多目标优化问题的边界问题。版权所有©2016 John Wiley & Sons， Ltd。
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.
登录
查看更多内容
影响因子：
1.1
作者：
P. Kouvelis;R. C. Carlson
通讯作者：
R. C. Carlson
了解多目标优化中的复杂性（Dagstuhl 研讨会 15031）
DOI：
--
发表时间：
2015
期刊：
Dagstuhl Reports
影响因子：
--
作者：
S. Greco;K. Klamroth;Joshua D. Knowles;G. Rudolph
通讯作者：
G. Rudolph
DOI：
--
发表时间：
2009
期刊：
Algorithmics of Large and Complex Networks
影响因子：
--
作者：
Stefan Ruzika;H. Hamacher
通讯作者：
H. Hamacher
DOI：
--
发表时间：
2018
期刊：
影响因子：
--
作者：
Jochen Gorski
通讯作者：
Jochen Gorski
具有 k-min 目标的多标准 0-1 背包问题
影响因子：
4.6
作者：
Aiying Rong;K. Klamroth;J. Figueira
通讯作者：
J. Figueira