Aarhus University Seal

Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review



This paper considers combinatorial optimization problems with an objective of type bottleneck, so the objective is to minimize the maximum cost among all elements in a feasible solution. For these problems, the sensitivity of an optimal solution to changes in parameters has received much less attention in existing studies than the computation of an optimal solution. This paper introduces methods for computing upper and lower tolerances which measure the amount of cost change needed in an element inside and outside an optimal solution, respectively, before that solution becomes non-optimal. Our main contribution is the development of efficient computation methods for bottleneck versions of the Linear Assignment Problem and the Minimum Spanning Tree Problem.

Original languageEnglish
JournalTheoretical Computer Science
Pages (from-to)1-21
Number of pages21
Publication statusPublished - Nov 2022

Bibliographical note

Publisher Copyright:
© 2022 The Author(s)

    Research areas

  • Bottleneck Spanning Tree Problem, Bottleneck objective, Combinatorial optimization, Linear Bottleneck Assignment Problem, Sensitivity analysis

See relations at Aarhus University Citationformats

ID: 283688896