Abstract:The regular set tolerance is an important term in sensitivity analysis. For combinatorial sum problems, e.g., the Traveling Salesman Problem, Shortest Path Problem and Minimum Spanning Tree Problem, it determines how much the sum of the costs of the elements of a set can be increased while ensuring that all current optimal solutions remain optimal. The regular set lower tolerance determines how much the sum of the costs of the elements of a set can be decreased while ensuring that the objective value of the optimal solution is not changed. We investigate a general method for computing regular (upper and lower) set tolerances in combinatorial sum problems. For the upper tolerance, we present a linear programming approach, and for the lower tolerances, three linear programming approaches, where the last two are novel and lead to recursive procedures for computation of the lower tolerances of all subsets of the given ground set. Furthermore, we give new upper bounds for set lower tolerances. For both upper and lower tolerances, we give an exact formula for sets of cardinality 2 and 3. Finally, we consider the computation of tolerances for the Minimum Spanning Tree Problem, give a formula for single tolerances, a lower bound for regular set upper tolerances and an exact formula for regular set lower tolerances.
From: Dmitry Panasenko [view email]
[v1]
Mon, 11 May 2026 13:22:34 UTC (21 KB)
[v2]
Thu, 30 Jul 2026 12:26:15 UTC (19 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。