Home > Research > Publications & Outputs > Output-sensitive complexity of multiobjective c...

Electronic data

  • Accepted manuscript

    Rights statement: This is the peer reviewed version of the following article Bökler F, Ehrgott M, Morris C, Mutzel P. Output-sensitive complexity of multiobjective combinatorial optimization. J Multi-Crit Decis Anal. 2017;24:25–36. https://doi.org/10.1002/mcda.1603 which has been published in final form at http://onlinelibrary.wiley.com/doi/10.1002/mcda.1603/full This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.

    Accepted author manuscript, 676 KB, PDF document

    Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License

Links

Text available via DOI:

View graph of relations

Output-sensitive complexity of multiobjective combinatorial optimization

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published
Close
<mark>Journal publication date</mark>1/01/2017
<mark>Journal</mark>Journal of Multi-Criteria Decision Analysis
Issue number1-2
Volume24
Number of pages12
Pages (from-to)25-36
Publication StatusPublished
<mark>Original language</mark>English

Abstract

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, i.e., its running time is bounded by a polynomial in the input and the output size. We provide both practical examples of MOCO problems for which such an efficient algorithm exists as well as problems for which no efficient algorithm exists under mild complexity theoretic assumptions.

Bibliographic note

This is the peer reviewed version of the following article Bökler F, Ehrgott M, Morris C, Mutzel P. Output-sensitive complexity of multiobjective combinatorial optimization. J Multi-Crit Decis Anal. 2017;24:25–36. https://doi.org/10.1002/mcda.1603 which has been published in final form at http://onlinelibrary.wiley.com/doi/10.1002/mcda.1603/full This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.