Output-sensitive Complexity of Multiobjective Combinatorial Optimization
Output-sensitive Complexity of Multiobjective Combinatorial Optimization
复制标题
多目标组合优化的输出敏感复杂度
DOI：
10.1002/mcda.1603
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
P. Mutzel
中科院分区：
文献类型：
--
作者：
F. Bökler;M. Ehrgott;C. Morris;P. Mutzel
我们研究多目标组合优化问题的输出敏感算法和复杂性。在这个计算复杂性框架中，如果一般枚举问题的算法对输出敏感，即其运行时间受输入和输出大小的多项式限制，则该算法被认为是有效的。我们提供了存在这种有效算法的多目标组合优化问题的实际例子，以及在温和复杂性理论假设下不存在有效算法的问题。
We study output‐sensitive algorithms and complexity for multiobjective combinatorial optimization problems. In this computational complexity framework, an algorithm for a general enumeration problem is regarded efficient if it is output‐sensitive, that is, its running time is bounded by a polynomial in the input and the output size. We provide both practical examples of multiobjective combinatorial optimization problems for which such an efficient algorithm exists as well as problems for which no efficient algorithm exists under mild complexity theoretic assumptions.
登录
查看更多内容
DOI：
10.1201/9781420010749.ch30
发表时间：
2018
期刊：
2006 IEEE 63rd Vehicular Technology Conference
影响因子：
--
作者：
B. Venkatachalam;David Fernández
通讯作者：
David Fernández
在具有多个目标的拟阵上
DOI：
--
发表时间：
1996
期刊：
影响因子：
--
作者：
E. Ehrgott
通讯作者：
E. Ehrgott
DOI：
10.1145/2699445
发表时间：
2015
期刊：
Journal of the ACM (JACM)
影响因子：
--
作者：
T. Brunsch;H. Röglin
通讯作者：
H. Röglin
通过资源受限的数据分析提供信息
DOI：
--
发表时间：
2011
期刊：
影响因子：
--
作者：
M. Backes;C. Bockermann;Fabian Bohnen;C. Borchert;F. Clevermann;B. Dusza;K. Fielitz;Leo N. Geppert;Anne;Melanie Heilmann;Christoph Ide;F. Jungermann;Timo Knaup;J. Köhne;B. Konrad;Dominik Kopczynski;Helena Kotthaus;Patrick Krümpelmann;Michel Lang;Pascal Libuschewski;Martin Marcel;Matthias Meier;N. Milke;Alexander Munteanu;D. Neise;Brian Niehöfer;Strah Nikolah;N. Piatkowski;Sascha Plazar;M. Preuß;M. Putzke;T. Ruhe;K. Rupp;Chris Schwiegelshohn;Dominic Siedhoff;Marco Stolpe;J. Streicher;Cornelia Tadros;Sylvie Temme;A. Thieler;Andreas Thom;Constantin Timm;M. Uellenbeck;T. Voigt;Daniel Weber
通讯作者：
Daniel Weber
枚举多目标组合优化问题极值非支配点的输出敏感算法
DOI：
10.1007/978-3-662-48350-3_25
发表时间：
2015
期刊：
影响因子：
--
作者：
F. Bökler;P. Mutzel
通讯作者：
P. Mutzel