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

DOI10.1016/J.TCS.2022.09.026MaRDI QIDQ2089667zbMATH OpenOpenAlexFDO

Authors Marcel Turkensteen, Gerold Jäger

Publication date 24 October 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.tcs.2022.09.026

zbMATH Keywords

bottleneck objectivebottleneck spanning tree problemcombinatorial optimizationlinear bottleneck assignment problemsensitivity analysis

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems
• Some Basics on Tolerances
• On the complexity of determining tolerances for ε-optimal solutions to min-max combinatorial optimization problems
• Sensitivity analysis for bottleneck assignment problems
• scientific article; zbMATH DE number 969937

Cites work

• Algorithms and Computation
• Algorithms for two bottleneck optimization problems
• Algorithms for updating minimal spanning trees
• An O(n) algorithm to solve the Bottleneck Traveling Salesman Problem restricted to ordered product matrices
• An addendum on: ``Sensitivity analysis of the optimal assignment
• An augmenting path method for solving linear bottleneck assignment problems
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• An optimal minimum spanning tree algorithm
• Assignment Problems
• Bottleneck flows in unit capacity networks
• Extending single tolerances to set tolerances
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• Improving the Hungarian assignment algorithm
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• Min-Max vs. Min-Sum vehicle routing: a worst-case analysis
• Mosaicking of aerial photographic maps via seams defined by bottleneck shortest paths
• On dual solutions of the linear assignment problem
• On min-max \(r\)-gatherings
• Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• Shortest paths algorithms: Theory and experimental evaluation
• Solution of a min-max vehicle routing problem
• Stability criteria in vector combinatorial bottleneck problems in terms of binary relations
• The Min-Max Spanning Tree Problem and some extensions
• Tolerance-based branch and bound algorithms for the ATSP

Cited in

(5)

• Assessing the effect of multiple cost changes using reverse set tolerances
• Computation of lower tolerances of combinatorial bottleneck problems
• Efficient computation of all tolerances in the sparse maxmin path problem
• Extending the definition of single and set tolerances
• Efficient online sensitivity analysis for the injective bottleneck path problem

Describes a project that uses

Uses Software

• LKH

This page was built for publication: Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2089667)