arxiv: 2605.10542 · v1 · submitted 2026-05-11 · 🧮 math.CO · math.OC

Recognition: no theorem link

Computation of Set Tolerances with Applications to the Minimum Spanning Tree Problem

Gerold J\"ager , Dmitrii Panasenko

Authors on Pith no claims yet

Pith reviewed 2026-05-12 04:52 UTC · model grok-4.3

classification 🧮 math.CO math.OC

keywords set tolerancesminimum spanning treesensitivity analysiscombinatorial optimizationlinear programmingupper toleranceslower tolerancesrecursive computation

0 comments

The pith

Linear programming methods compute regular upper and lower set tolerances for combinatorial sum problems, with exact formulas and recursive procedures for the minimum spanning tree problem.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a general approach to finding regular set tolerances, which measure how much the summed costs of a chosen set of elements can increase or decrease while preserving the optimality of current solutions in problems whose objective is a sum of costs. It gives one linear programming formulation for upper tolerances and three for lower tolerances, with two of the lower-tolerance approaches being new and supporting recursive calculation of the values for every subset of the ground set. New upper bounds on lower tolerances are stated, together with closed-form expressions that hold for every set of two or three elements. When specialized to the minimum spanning tree problem the same framework produces a direct formula for the tolerance of any single edge, a lower bound on the upper tolerance of any set of edges, and an exact expression for the lower tolerance of any set of edges.

Core claim

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. We give new upper bounds for set lower tolerances and exact formulas for sets of cardinality 2 and 3. For the Minimum Spanning Tree Problem we give a formula for single tolerances, a lower bound for regular set upper tolerances and an exact formula for regular set lower tolerances.

What carries the argument

Linear programming models that encode the requirement that every current optimal solution remains optimal after a uniform cost change is applied to all members of a designated set, thereby isolating the largest admissible change (the tolerance).

Load-bearing premise

The objective value of every feasible solution equals the sum of the costs of its elements, so that a change to the cost of any collection of elements shifts the objective by exactly that amount.

What would settle it

A small MST instance in which the value returned by the stated lower-tolerance formula for a chosen set of edges is smaller than the actual largest decrease that leaves the original tree optimal.

Figures

Figures reproduced from arXiv: 2605.10542 by Dmitrii Panasenko, Gerold J\"ager.

**Figure 1.** Figure 1: Undirected weighted graph with 7 vertices, 13 edges; with one of MSTs in bold face and upper/lower tolerances given in brackets. We illustrate the computation of single upper tolerances using the edge e = {v1, v2} as an example. Since e ∈ E(T ∗ ), we apply Theorem 17(a) to compute u ′ P (e). The non-tree edge g = {v1, v5} with cost 2 is the edge with the smallest cost among all non-tree edges. The path PT … view at source ↗

**Figure 2.** Figure 2: For the example graph given in [PITH_FULL_IMAGE:figures/full_fig_p028_2.png] view at source ↗

**Figure 3.** Figure 3: For the example graph given in [PITH_FULL_IMAGE:figures/full_fig_p029_3.png] view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives two new LP formulations for lower set tolerances that support recursive computation over all subsets, plus exact formulas for small sets and the MST.

read the letter

This paper develops linear programming approaches to compute regular set upper and lower tolerances for combinatorial sum problems like the traveling salesman, shortest path, and minimum spanning tree problems. The key new pieces are two LP formulations for the lower tolerances that lead to recursive procedures for finding the values for all subsets at once. They also add new upper bounds on the lower tolerances and give exact formulas for sets with two or three elements. For the MST specifically, there is a formula for single tolerances, a lower bound for regular set upper tolerances, and an exact formula for regular set lower tolerances. The approach stays within standard LP models for these tolerances and extends them to handle sets rather than single elements. The recursive computation is a practical step forward because it avoids solving a separate LP for each subset. The exact formulas for small cardinalities and the MST results are clean and could be implemented directly in code for sensitivity checks. One limitation is that the paper does not report any numerical experiments or running times. It is not clear how the recursive method scales compared with solving the LPs independently or with other existing tolerance algorithms. A reader would also want to see how these new bounds compare in tightness to previous work on the same problems. The paper is aimed at researchers working on sensitivity analysis in combinatorial optimization, particularly those dealing with network problems. A reader who needs to compute tolerances for many subsets or who works on MST variants will find the formulas and procedures directly applicable. The work shows clear thinking about the problem structure and engages with the relevant literature on tolerances. It deserves a serious referee because the claims are specific and the methods are laid out in a way that can be checked. I would recommend sending it for peer review.

Referee Report

0 major / 3 minor

Summary. The paper develops a general framework for computing regular upper and lower set tolerances in combinatorial sum problems (where the objective equals the sum of selected element costs), including TSP, shortest-path, and MST instances. It gives one LP formulation for upper tolerances and three for lower tolerances, with the final two claimed to be novel and to yield recursive procedures that compute lower tolerances for every subset of the ground set. New upper bounds on set lower tolerances are stated, together with closed-form expressions for sets of cardinality 2 and 3. For the MST problem the authors supply an explicit formula for single-element tolerances, a lower bound on regular set upper tolerances, and an exact formula for regular set lower tolerances.

Significance. If the LP constructions and recursive procedures are correct, the work supplies a systematic way to obtain set-wise sensitivity information that goes beyond the single-element tolerances already studied in the literature. The recursive lower-tolerance routines and the MST-specific closed forms could be directly useful for robustness analysis of spanning-tree solutions; the exact formulas for |S|=2,3 also provide immediate, parameter-free checks for small sets.

minor comments (3)

The abstract and introduction should explicitly compare the two novel LP formulations for lower tolerances with the existing single-tolerance LP literature (e.g., the formulations of Gal and Greenberg or subsequent MST-tolerance papers) so that the claimed novelty is immediately verifiable.
The recursive procedures are described at a high level; a short pseudocode block or a worked numerical example on a 5-vertex MST instance would clarify the recursion depth and the number of LPs solved per subset.
Notation for regular upper/lower tolerances (e.g., the symbols used for the set tolerances themselves) should be introduced once and used uniformly; several passages appear to switch between descriptive phrases and symbols without a central definition table.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. As the report lists no specific major comments, we have no points to address point-by-point.

Circularity Check

0 steps flagged

No significant circularity; the LP formulations and formulas build on standard combinatorial optimization without reducing to self-defined inputs.

full rationale

The paper presents LP approaches for upper and lower set tolerances in sum-objective combinatorial problems, with novel recursive procedures for lower tolerances and specific formulas for MST. These are derived from the problem definitions and standard LP duality or sensitivity analysis, not from fitting parameters to the target quantities or self-citations that bear the load. The MST results follow from the general method applied to the spanning tree structure. No step equates a prediction to its input by construction, and external benchmarks like LP solvers make the claims independently verifiable.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard domain assumptions of combinatorial sum problems and linear programming duality; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

domain assumption The objective function of the combinatorial problem is the sum of costs of the selected elements.
This is the explicit setting stated in the abstract for defining regular set tolerances.

pith-pipeline@v0.9.0 · 5519 in / 1353 out tokens · 57923 ms · 2026-05-12T04:52:16.696781+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

Cacuci, D.: Sensitivity and Uncertainty Analysis, vol. I. Chapman & Hall/CRC (2003)

work page 2003
[2]

Journal of Computer and System Sciences16, 334–344 (1978)

Chin, F., Houck, D.: Algorithms for updating minimal spanning trees. Journal of Computer and System Sciences16, 334–344 (1978)

work page 1978
[3]

John Wiley & Sons, Ltd (1997)

Cook, W., Cunningham, W., Pulleyblank, W., Schrijver, A.: Combinatorial Opti- mization. John Wiley & Sons, Ltd (1997)

work page 1997
[4]

In: Goldberg, A., Zhou, Y

Dong, C., Jäger, G., Richter, D., Molitor, P.: Effective tour searching for TSP by contraction of pseudo backbone edges. In: Goldberg, A., Zhou, Y. (eds.) Proc. 5th International Conference on Algorithmic Aspects in Information and Management, AAIM 2009, Lecture Notes in Computer Science, vol. 5564. pp. 175–187. Springer (2009)

work page 2009
[5]

Computers and Operations Research39(2), 291– 298 (2012)

Germs, R., Goldengorin, B., Turkensteen, M.: Lower tolerance-based branch and bound algorithms for the ATSP. Computers and Operations Research39(2), 291– 298 (2012)

work page 2012
[6]

In: Neogy, S., Bapat, R., Das, A., Parthasarathy, T

Ghosh, D., Goldengorin, B., Gutin, G., Jäger, G.: Tolerance-based Algorithms for the Traveling Salesman Problem. In: Neogy, S., Bapat, R., Das, A., Parthasarathy, T. (eds.) Mathematical Programming and Game Theory for Decision Making, pp. 47–59. World Scientific, New Jersey (2008)

work page 2008
[7]

Journal of Computer Science2(9), 716–734 (2006)

Goldengorin, B., Jäger, G., Molitor, P.: Tolerances applied in combinatorial opti- mization. Journal of Computer Science2(9), 716–734 (2006)

work page 2006
[8]

European Journal of Operations Research126(1), 106–130 (2000)

Helsgaun, K.: An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operations Research126(1), 106–130 (2000)

work page 2000
[9]

Journal of Heuristics20(1), 107–124 (2014)

Jäger, G., Dong, C., Goldengorin, B., Molitor, P., Richter, D.: A backbone based TSP heuristic for large instances. Journal of Heuristics20(1), 107–124 (2014)

work page 2014
[10]

Discrete Applied Mathematics247, 197–215 (2018)

Jäger, G., Turkensteen, M.: Extending single tolerances to set tolerances. Discrete Applied Mathematics247, 197–215 (2018)

work page 2018
[11]

Discrete Applied Mathematics354, 279–300 (2024)

Jäger, G., Turkensteen, M.: Assessing the effect of multiple cost changes using reverse set tolerances. Discrete Applied Mathematics354, 279–300 (2024)

work page 2024
[12]

Discrete Optimization56, 100887 (2025)

Jäger, G., Turkensteen, M.: Computation of lower tolerances of combinatorial bot- tleneck problems. Discrete Optimization56, 100887 (2025)

work page 2025
[13]

Operations Research Letters65, 107407 (2026)

Jäger, G., Turkensteen, M.: Extending the definition of single and set tolerances. Operations Research Letters65, 107407 (2026)

work page 2026
[14]

Information Processing Letters14(1), 30–33 (1982)

Tarjan, R.: Sensitivity analysis of minimum spanning trees and shortest path trees. Information Processing Letters14(1), 30–33 (1982)

work page 1982
[15]

Journal of Global Optimization68, 601–622 (2017) 16 G

Turkensteen, M., Malyshev, D., Goldengorin, B., Pardalos, P.: The reduction of computation times of upper and lower tolerances for selected combinatorial opti- mization problems. Journal of Global Optimization68, 601–622 (2017) 16 G. Jäger, D. Panasenko Appendix A. Proof of Theorem 8 In the following letS∗ be an optimal solution forP. (a)W.l.o.g., assume ...

work page 2017
[16]

Thenα ∗ =u ′ P(E)holds. Consider the following LP: maximizeα 1 +α 2 +α 3 subject toα 1 +α 2 +α 3 ≤f c(D−(E))−c ∗ (36) α1 +α 2 ≤u ′ P(e1, e2)(37) α1 +α 3 ≤u ′ P(e1, e3)(38) α2 +α 3 ≤u ′ P(e2, e3)(39) α1 ≤u ′ P(e1)(40) α2 ≤u ′ P(e2)(41) α3 ≤u ′ P(e3)(42) α1, α 2, α 3 ≥0 We call the LP above LP2. Let#»α′ = (α′ 1, α′ 2, α′ 3)be an optimal solution of LP2, and...

work page
[17]

We show thatV1,2,3 =α ′

By Theorem 13,α′ =l ′ P(E)holds. We show thatV1,2,3 =α ′. First, letα ′ =∞. Then there exists ani∈[3]withα ′ i =∞. W.l.o.g., let α′ 1 =∞. Then because of (97), (98), (99), (101) it holds that fc(D+(E))−c ∗ =l ′ P(e1, e2) =l ′ P(e1, e3) =l ′ P(e1) =∞. It follows thatV1,2,3 =∞. Second, letV 1,2,3 =∞. If there existsi∈[3]such thatl ′ P(ei) =∞, then by Theore...

work page