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

Research

Associated organisational units

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/Magazine › Journal article › peer-review

Published

Standard

Output-sensitive complexity of multiobjective combinatorial optimization. / Bökler, Fritz; Ehrgott, Matthias; Morris, Christopher et al.
In: Journal of Multi-Criteria Decision Analysis, Vol. 24, No. 1-2, 01.01.2017, p. 25-36.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Bökler, F, Ehrgott, M, Morris, C & Mutzel, P 2017, 'Output-sensitive complexity of multiobjective combinatorial optimization', Journal of Multi-Criteria Decision Analysis, vol. 24, no. 1-2, pp. 25-36. https://doi.org/10.1002/mcda.1603

APA

Bökler, F., Ehrgott, M., Morris, C., & Mutzel, P. (2017). Output-sensitive complexity of multiobjective combinatorial optimization. Journal of Multi-Criteria Decision Analysis, 24(1-2), 25-36. https://doi.org/10.1002/mcda.1603

Vancouver

Bökler F, Ehrgott M, Morris C, Mutzel P. Output-sensitive complexity of multiobjective combinatorial optimization. Journal of Multi-Criteria Decision Analysis. 2017 Jan 1;24(1-2):25-36. doi: 10.1002/mcda.1603

Author

Bökler, Fritz ; Ehrgott, Matthias ; Morris, Christopher et al. / Output-sensitive complexity of multiobjective combinatorial optimization. In: Journal of Multi-Criteria Decision Analysis. 2017 ; Vol. 24, No. 1-2. pp. 25-36.

Bibtex

@article{7c03f99a71a54637a69d68e3a9906774,
title = "Output-sensitive complexity of multiobjective combinatorial optimization",
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.",
author = "Fritz B{\"o}kler and Matthias Ehrgott and Christopher Morris and Petra Mutzel",
note = "This is the peer reviewed version of the following article B{\"o}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.",
year = "2017",
month = jan,
day = "1",
doi = "10.1002/mcda.1603",
language = "English",
volume = "24",
pages = "25--36",
journal = "Journal of Multi-Criteria Decision Analysis",
issn = "1057-9214",
publisher = "John Wiley and Sons Ltd",
number = "1-2",

}

RIS

TY - JOUR

T1 - Output-sensitive complexity of multiobjective combinatorial optimization

AU - Bökler, Fritz

AU - Ehrgott, Matthias

AU - Morris, Christopher

AU - Mutzel, Petra

N1 - 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.

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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.

AB - 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.

U2 - 10.1002/mcda.1603

DO - 10.1002/mcda.1603

M3 - Journal article

VL - 24

SP - 25

EP - 36

JO - Journal of Multi-Criteria Decision Analysis

JF - Journal of Multi-Criteria Decision Analysis

SN - 1057-9214

IS - 1-2

ER -