Global Sensitivity Analysis for Bottleneck Assignment Problems

In assignment problems, decision makers are often interested in not only the optimal assignment, but also the sensitivity of the optimal assignment to perturbations in the assignment weights. Typically, only perturbations to individual assignment weights are considered. We present a novel extension of the traditional sensitivity analysis by allowing for simultaneous variations in all assignment weights. Focusing on the bottleneck assignment problem, we provide two different methods of quantifying the sensitivity of the optimal assignment, and present algorithms for each. Numerical examples as well as a discussion of the complexity for all algorithms are provided.


Introduction
In the classic assignment problem, we seek a one to one matching of a set of agents to a set of tasks which optimises some assignment cost. For example, Nam and Shell (2015) consider a vehicle routing problem, assigning destinations to vehicles in order to minimise the time taken for all vehicles to reach their destinations within a road network. Assignment problems have a wide variety of applications, such as resource allocation (Harchol-Balter et al. (1999)), scheduling (Carraresi and Gallo (1984), Adams et al. (1988)), and the aforementioned autonomous vehicle routing (Shames et al. (2017), Nam and Shell (2015), Arslan et al. (2007)). Pentico (2007) review a variety of assignment objectives, such as the sum of all the assigned weights (linear assignment) or the difference between the maximum and minimum weight assignment (balanced assignment problem). Here we focus on the bottleneck assignment problem (BAP), which minimises the maximum assigned weight within the assignment. The BAP is particularly applicable in minimum time scenarios, ensuring that a team of agents working in parallel complete their tasks in minimum time. For the bottleneck assignment problem there are many algorithms which provide solution in polynomial time, reviewed in Pentico (2007) and Pferschy (1997).
In many applications the weight associated with the assignment of an agent to a task carries with it some uncertainty. Measurement errors, communication delays, or a dynamic environment may contribute to an inaccurate estimate of an assignment weight. If the uncertainty is known a-priori a minimax approach may be used, identifying an assignment which minimises the assignment cost for the worst case realisation of the uncertainty. However, this is typically a conservative solution. In applications where such a-priori knowledge is unavailable/impractical, or a conservative solution undesirable, we instead employ sensitivity analysis.
Sensitivity analysis characterises how perturbations to the inputs affect the output. In the case of uncertainty in the assignment weights, a sensitivity analysis informs the decision maker in which ways the optimal assignment may change, given perturbations to the measured weights. We adopt Type II sensitivity analysis from Koltai and Terlaky (2000), or equivalently the sensitivity of the optimal basis as in Jansen et al. (1997). Type II sensitivity analysis characterises the set of weight perturbations to which the optimal assignment is invariant. In the sensitivity analysis of linear programs, as in Jansen et al. (1997), the perturbations are restricted to an individual element of the canonical weight vector, while the remaining elements are held fixed. However, due to the additional structure of a BAP, we are able to extend the sensitivity analysis to simultaneous perturbations in all of the weights. We consider this a more applicable formulation of assignment sensitivity, as perturbations to the measured weights occur simultaneously if tasks are carried out in parallel.

Literature Review
Due to the assignment problem's popularity in network theory, there exist various methods incorporating uncertainty in the assignment weights. Roughly characterised, we have those which compute robust assignments with a priori knowledge of uncertainty, and those which characterise some notion of sensitivity of the assignment to perturbations. Volgenant and Duin (2010) presents several robust optimisation approaches to the bottleneck assignment problem, with interval assumptions on the possible weight values. Fu et al. (2015) and Kasperski and Zieliński (2013) begin with a set of possible scenarios, and compute robust minimax assignment solutions by blending those scenarios. Without a priori knowledge of the uncertainty, Lin and Wen (2003) and Volgenant (2006) present the sensitivity of the linear assignment to perturbations in a single weight, based on the dual variables arising from a primal-dual optimisation. Ramaswamy et al. (2005) provide similar results in the shortest path and maximum cut network problems, which can be shown to be equivalent formulations to the linear assignment problem. However, they do not consider simultaneous weight perturbations in multiple edges. Both Nam and Shell (2015) and Lin and Wen (2007) present sensitivity analysis algorithms for the linear assignment, allowing for perturbations in an assigned edge as well as in edges adjacent to the assigned edge (i.e., a row/column of the weight matrix). However, these analyses do not take into account simultaneous perturbations in multiple assigned edges. Wood et al. (2020) present an assignment and collision avoidance algorithm, which utilises a bottleneck assignment sensitivity estimation. However, they consider only positive weight perturbations, and only in the edges which are assigned.
Most similar to the analysis presented in this paper are the results from Sotskov et al. (1995), which discusses the largest uniform bound on all of the input weight perturbations to maintain optimality for both the linear and bottleneck assignment problems. The results from Sotskov et al. (1995) will coincide with the smallest magnitude perturbation bound in our results, discussed in Section 2 and Section 5.
Previously, Michael et al. (2019) presented a preliminary sensitivity analysis which allowed for simultaneous perturbations in all assignment weights. In this paper we build on these results, providing a complete theoretical framework for understanding the sensitivity of the bottleneck assignment problem, as well as improved algorithmic results. For a given bottleneck assignment, the methods we provide construct intervals within which the assignment weights may vary while preserving the optimality of the assignment. We further show these are the lexicographically largest set of allowable perturbations, as defined in Section 2. We provide algorithms to compute these intervals, as well as numerical examples and complexity analyses.

Organisation of Paper
Section 2 formalises the assignment problem, as well as the definitions of sensitivity used in this work. Section 3 establishes the main theoretical tools used, and applies them to solve the problem of bottleneck edge sensitivity. Using these, the bottleneck assignment sensitivity problem is addressed in Section 4. In Section 5, we discuss the complexities of the provided algorithms. Conclusions are presented in Section 6.

Preliminaries and Problem Formulation
n×m over the extended reals i.e., R := R ∪ {−∞, +∞}, where n := |V A | and m := |V T | such that m ≤ n, and w ij is the weight associated with edge (i, j), or +∞ if (i, j) ∈ E. We also define a set of binary decision variables π := {π ij | π ij ∈ {0, 1}, (i, j) ∈ E}. The bottleneck assignment problem can be formulated as If π ij = 1 then we say that vertex i is assigned to vertex j or the edge (i, j) is assigned. Constraints (1b) and (1c) ensure that every vertex is assigned to at most one other vertex, and that all vertices from the smaller vertex set V T are assigned. Along with the set of binary decision variables π, we define an assignment Π = {(i, j) | π ij = 1} to be the set of edges which are assigned in π. We refer to an assignment which is an optimiser of (1) as a bottleneck assignment.
Definition 1 (Feasible Assignments Set). For a bipartite graph G with weights W ∈ R n×m , define P n×m as the set of all possible assignments Π satisfying the constraints (1b)-(1c).
We make the following standing assumption throughout this paper.
Assumption 1. The set P n×m as defined in Definition 1 is nonempty.
We define a mapping BAP : R n×m → P n×m which maps the weight matrix to the set of optimisers of (1).
Definition 2 (Allowable Perturbation). For a given bipartite graph G with weights W , let Π ∈ BAP(W ), i.e. Π is an optimiser of (1) over the weights W . A perturbation P ∈ R n×m is allowable with respect to Π if Π ∈ BAP(W + P ). If Π ∈ BAP(W + P ), then P is not allowable with respect to Π.
For a given graph G and weights W with optimiser Π ∈ BAP(W ), identifying if Π is an optimiser over the perturbed weights W + P is, in general, equivalent to solving a new assignment problem. In this sensitivity analysis, we provide a sufficient but not necessary condition for the invariance of the optimal assignment, in the form of an interval test.
Let Λ ⊆ R n×m be an n × m array of intervals over the extended reals.
For each edge (i, j) ∈ E, let Λ ij := [−λ ij , λ ij ] be the interval corresponding to edge (i, j). For any perturbation P ∈ R n×m , we write P ∈ Λ if Finally, we label Λ allowable relative to Π if for all P ∈ Λ, P is an allowable perturbation relative to Π as in Definition 2. Throughout this paper we will require that 0 n×m ∈ Λ, or equivalently λ ij , λ ij are non-negative. To order the intervals we use the lexicographic ordering.
The lexicographic ordering is inspired by alphabetical ordering of words, such as in a dictionary. Let Λ ⊆ R n×m be an array of intervals. Define a mapping ρ k (Λ) which returns the k-th minimal magnitude upper or lower bound of any of the intervals in Λ, which will be used to order these intervals.
Definition 3 (Lexicographic Ordering of Interval Arrays). For two arrays of intervals, then Λ a , Λ b are compared by ρ 2 (Λ a ), ρ 2 (Λ b ), and so on. Let the operator lexmax (I) return the lexicographic maximal element of I denoted by Λ * ∈ I where I is a set of interval arrays and Λ * Λ, ∀ Λ ∈ I, with denoting the lexicographic ordering.
Lexicographic maximisation thus maximises the minimum element, then the second minimum, and so on.
Problem 1. For a given graph G = (V, E) with weights W and optimiser Π ∈ BAP(W ), construct the lexicographically largest array of intervals For a given graph G with weights W and Π ∈ BAP(W ), let Problem 1 is then equivalent to finding Λ * ⊂ R n×m such that Before solving Problem 1, or equivalently constructing Λ * from (4), we will solve a simpler related problem. To this aim, we define bottleneck edges below.
Definition 4 (Bottleneck Edges). For a bipartite graph G with weights W , the maximal weight edges in all bottleneck assignments are the bottleneck edges of G.
We define a new mapping E : R n×m → E which takes the weights and returns the bottleneck edges. We define a perturbation P ∈ R n×m as edge allowable relative to a bottleneck edge e * ∈ E(W ) if e * ∈ E(W + P ). Note that we use either e or (i, j) to denote an edge interchangeably. We formulate the problem of the bottleneck edge sensitivity similarly to the bottleneck assignment sensitivity.
Problem 2. For a given bipartite graph G = (V, E) with weights W and e * ∈ E(W ), construct the lexicographically largest array of intervals For a bipartite graph G with weights W and e * ∈ E(W ), let Problem 2 is then equivalent to finding Λ * ⊂ R n×m such that This problem will be addressed in Section 3. The theoretical tools used to solve Problem 2 will be central to solving Problem 1. However, before proceeding any further, we introduce exclusive sets which will be used throughout the paper.

Exclusive Sets
We begin by defining the central theoretical tool of this paper, which we term the exclusive set with respect to some e ∈ E, denoted S e .
Definition 5 (Exclusive Set). For a bipartite graph G we define S e * to be an exclusive set with respect to an edge e * ∈ E if it satisfies the following properties: 1. S e * ⊂ E; 2. e * ∈ S e * ; 3. P n×m = P e * ∪ e∈S e * P e where P e ⊂ P n×m is the subset of assignments which assign edge e.
For a bipartite graph G, define S e to be the set of all exclusive sets for e ∈ E.
The third property of an exclusive set S e * , as defined above, is critical in connecting the exclusive set to the bottleneck assignment problem. In words, we may rephrase the property as: All assignments over the graph either contain the edge e * , or an edge from the exclusive set. The connection between the bottleneck assignment problem and the exclusive set is made clear in Lemma 1.
Lemma 1. For a bipartite graph G with weights W , let e * ∈ E. There exists an assignment Π ∈ P e * and an exclusive set S e * ∈ S e * that satisfy if and only if e * ∈ E(W ), i.e., the edge e * is a bottleneck edge, and Π is a bottleneck assignment.
Proof. Appendix A.
Lemma 1 establishes the equivalence of e * being a bottleneck edge and the existence of an exclusive set and assignment Π satisfying (7) and (8) relative to e * . This tool allows a reformulation of (4) and (6), in which we replace the sets L A and L E defined in (3) and (5), respectively, with sets re-defined by the conditions from Lemma 1.

Bottleneck Edge Sensitivity
We now apply Lemma 1 to reformulate and solve Problem 2. For a bipartite graph G with weights W , let e * ∈ E(W ). By Lemma 1, there exist an assignment Π and an exclusive set S e * satisfying (7) and (8), respectively, relative to e * . We define the following sets of interval arrays: The main result of this section is presented below.
Proof. Appendix B.
Remark 1. In Theorem 1, we note that (9)-(10) are defined only by the bounds λ e , ∀e ∈ S e * ∪ {e * } and λ e , ∀e ∈ Π. All other upper and lower bounds are not involved in the set definitions, and are thus unbounded in the lexicographic maximisation. We use λ e = ∞ to denote that any positive perturbation is allowable, similarly using −λ e = −∞ for negative perturbations.
In Theorem 1 we reformulate Problem 2, using auxiliary variables S e * ∈ S e * and Π ∈ P e * . In the following section we provide an algorithm to construct Λ * = lexmax(L 0 ∩ X S e * ∩ A Π ), for a given exclusive set S e * and assignment Π. Finally, we conclude with algorithms to construct the particular exclusive set S e * ∈ S e * and assignment Π ∈ P e * such that completing the solution to Problem 2.

Constructing Edge Allowable Perturbation Intervals
In this section we construct lexmax(L 0 ∩ X S e * ∩ A Π ) for a given exclusive set and assignment.
Proof. Appendix C.

Constructing the Exclusive Set and Assignment
Algorithm 1 constructs the lexicographically largest set of allowable perturbation intervals given an exclusive set and bottleneck assignment. We now show how to select the exclusive set S e * and bottleneck assignment Π such that We begin with the bottleneck assignment Π.
Informally, the assignment in which the largest weight is minimised, the second largest weight is minimised, . . . is the lexicographic assignment. The lexicographic assignment can be seen as a continuation of the bottleneck assignment objective, and can be computed in polynomial time, Burkard and Rendl (1991).
Lemma 3. For a given set of weights W and an exclusive set S e * , the lexicographic assignment Π with maximal weight edge e * satisfies Proof. Appendix D.
We now turn to the choice of the exclusive set S e * which yields the lexicographically largest array of intervals from Algorithm 1.
In Algorithm 2, the initial bottleneck edge is found, removed from the graph by setting its weight to ∞, and the subsequent bottleneck edge is Algorithm 2: Algorithm to Construct S e * Data: W, e * Result: S e * 1 S e * ← {} ; 2 w e * ← ∞ ; // ∞ may be any suitably large constant 3 e ← E(W ) ; found. If the new bottleneck edge has finite weight, it is added to the set S e * . This repeats until the bottleneck edge has weight ∞, in which case there are no assignments left with the remaining edges of the graph. In order to prove the output of Algorithm 2 has the requisite properties, discussed in Lemma 4, we place the following restriction on graph G.
Assumption 2. For the bipartite graph G with weights W , the bottleneck edge e ∈ E(W ) at each iteration of Algorithm 1 is unique.
Assumption 2 is trivially satisfied if all edge weights are distinct.
Lemma 4. Given a weight matrix W with a bottleneck edge e * ∈ E(W ), the set of edges returned from Algorithm 2 is an exclusive set S e * relative to e * as defined in Definition 5. If Assumption 2 holds, then for a given bottleneck assignment Π ∈ P e * the exclusive set returned from Algorithm 2 satisfies Proof. Appendix E.
Corollary 1. Given a weight matrix W with a bottleneck edge e * ∈ E(W ), let S e * and Π be the exclusive set returned from Algorithm 2 and the lexicographic assignment, respectively. With G, S e * , Π, and e * as inputs, the array of intervals Λ * returned from Algorithm 1 satisfies Λ * = lexmax(L 0 ∩ L E ), and thus is the solution of Problem 2.
Proof. By Theorem 1, we have that there exists an exclusive set and assignment such that (11) is true. By Lemma 2, we have that Λ * from Algorithm 1 is the lexicographically largest array of intervals satisfying (9)-(10) for a given exclusive set and assignment. By Lemmas 3 and 4, we have that S e from Algorithm 2 and the lexicographic assignment are inputs which lexicographically maximise the Λ * output from Algorithm 1, therefore Λ * is the solution to Problem 2. The bottleneck edge of this weight matrix is e * = (1, 3), with weight 63. We define the set S e * as it is returned from Algorithm 2, S e * = {(2, 2), (1, 2), (2, 3)}. With the lexicographic assignment Π = {(2, 1), (3, 2), (1, 3)} and the aforementioned S e * , the lexicographically largest allowable perturbation intervals array is given by where L 0 , X S e * , A Π are defined as in Theorem 1. The elements of interval array Λ * are presented in Table 1.  It is simple to verify that any perturbation P ∈ Λ * satisfies e * ∈ E(W +P ).

Bottleneck Assignment Sensitivity
In this section we solve Problem 1 by providing Algorithm 3 to construct Λ * = lexmax(L 0 ∩L A ). In the previous section, we separated the construction of S e * and Π from the construction of Λ * . However, for Problem 1, we construct Λ * directly, relying on the previously established theory of exclusive sets only in the proof of the results. We first make an assumption on the structure of the weighted graph, analogous to Assumption 2.

Assumption 3. The bottleneck edges for all constructed graphs in Algorithm 3 are unique.
This assumption may be relaxed, however, it will lead to a quite cumbersome set of edge cases being included in the logic of Algorithm 3 and the proof of the following theorem without providing much insight into the nature of the problem.
Theorem 2. For a bipartite graph G with weights W , let Π ∈ BAP(W ). If Assumption 3 holds, then the array of intervals Λ * returned from Algorithm 3 satisfies for L A defined in (3). Equivalently, Λ * is the solution to Problem 1.
Proof. For a given bipartite graph G with weights W and Π ∈ BAP(W ), let Λ * be the array of intervals returned from Algorithm 3. We first prove by contradiction that there exists no lexicographically larger Λ ′ ∈ L 0 ∩ L A , by showing that a lexicographically larger set of intervals must contain an unallowable perturbation. We then show that Λ * ∈ L 0 ∩L A , which completes the proof. With the addition of Lemma 5 in Appendix F, the proof of this Theorem follows a similar line of reasoning as that of Lemma 4. For the complete proof, see Appendix G.
In Algorithm 3, we use B[e j ] to indicate the element of B ∈ R n×m corresponding to edge e j . We also use ∞ to denote a sufficiently large number such that when applied to a weight element the corresponding edge can be considered "removed" from the graph. Prior to presenting Algorithm 3, we first discuss the key steps and motivations. For the given assignment Π, we focus on a single edge e ∈ Π. Clearly, if there exists a perturbation P ∈ Λ and an assignment Π ′ = Π such that w e ′ +p e ′ < w e +p e , ∀e ′ ∈ Π ′ , then P cannot be an allowable perturbation and by extension Λ is not allowable. Algorithm 3 thus begins with all bounds of Λ unset (labeled with ∞), and iterates the following steps: 1. For each e ∈ Π and for each e ′ ∈ E, compute the lexicographically largest λ e , λ e ′ such that w e + λ e = w e ′ − λ e ′ , for whichever of the two λ e , λ e ′ are unset 1 . Store the resulting value in B e [e ′ ].(Update function in line 5) 2. For each e ∈ Π, find the bottleneck edge b e = E(B e ). The edge b e is a maximal weight edge of an assignment Π ′ for which there exists p ≤ B e [e ′ ] such that w e + p ≥ w e ′ − p, ∀e ′ ∈ Π ′ . Letê be the edge for which the weight of E(Bê) is less than or equal to the weight of E(B e ), ∀e ∈ Π, and letb = E(Bê). (Lines 6 & 8) 3. Update the bounds such that wê + λê = w bê − λ bê . (Lines 9-17) We conclude by implementing Algorithm 3 on the same example as in Section 3, to highlight the differences between the measures of sensitivity.
We can see in this case that either the allowable perturbation intervals are identical to the ones in Example 1, or strictly larger. However, this will not be true in general. Although the intervals Λ * corresponding to the bottleneck assignment sensitivity will be lexicographically larger, they may include more bounded edges than the intervals for the bottleneck edge sensitivity. For comparison, we will show the results from Sotskov et al. (1995), over the same example. Further explanation of these results are included in Section 5.

Computational Complexity
In this section we will provide a brief accounting of the complexity of the algorithms provided, as well as a comparison to the results from Sotskov et al. (1995). We first note that, in the computation of the bottleneck edge sensitivity as well as the bottleneck assignment sensitivity, we are iteratively running a bottleneck assignment solver on a graph, removing or modifying one edge weight at a time. Unsurprisingly, we can take advantage of the information from the previous iteration, to dramatically reduce the computational complexity. Using an augmenting path solver, such as from Punnen and Nair   (1994), we may "warm start" the solver with the previously optimal bottleneck assignment, removing only the modified edge. In this case, the algorithm need run only a single augmenting path search with complexity O(|V|), instead of finding bottleneck assignment solution with complexity O(|V| |E||V|).
We begin with the computational complexity of the bottleneck edge sensitivity. To compute the bottleneck edge sensitivity of a given e * ∈ BAP(W ), we compute • The lexicographic assignment Π.
• The exclusive set as returned from Algorithm 2.
• The lexicographically largest Λ * defined by the previous two steps, as in Algorithm 1. For a bipartite graph G = (V 1 ∪ V 2 , E), let n = |V 1 | + |V 2 | and m = |E|. Algorithm 2 requires O(m) iterations of a bottleneck assignment solver, although as noted previously, each iteration is only a single augmenting path search with complexity O(n). Note this is not true without Assumption 2. The complexity of computing the intervals Λ * is then O(L(n, m) + nm + m), where L(n, m) is the computational complexity of constructing the lexicographic assignment. For a simple example, we assume the graph is square and dense, i.e. |V 1 | = |V 2 | and E = V 1 × V 2 , and that the bottleneck edge of each subgraph of G is unique. Then the lexicographic assignment may be computed as O(n) iterations of the augmenting path solver, which yields a complexity of O(n 2 + n 3 + n 2 ) = O(n 3 ). This simplification shows that the computation of the exclusive set in Algorithm 2, which requires O(n 2 ) iterations of the bottleneck assignment solver, dominates the complexity. For the complexity of the bottleneck assignment sensitivity, we note that there are O(m) iterations of Algorithm 3, and at each iteration we update O(n) of the constructed graphs B e , ∀ e ∈ Π. The complexity is then O(nB(n, m) + n 2 m), for B(n, m) the complexity of the bottleneck assignment solver over the given graph. Using the complexity of the bottleneck assignment algorithm from Punnen and Nair (1994), and assuming a square and dense graph as before, this yields a complexity of O(n 3.5 + n 4 ) = O(n 4 ).
In the introduction, we mentioned the most similar work found in the literature to the presented was Sotskov et al. (1995). In their work, they construct a "sensitivity radius" σ(G), which we may interpret in the notation of this paper as the maximum scalar σ ∈ R + such that all perturbations P σ := {p ij ∈ [−σ, σ] | (i, j) ∈ E} are allowable. Letting Λ σ be the array of intervals with lower and upper bound −σ, σ, we then have that ρ 1 (Λ * ) = ρ 1 (Λ σ ) and ρ i (Λ * ) ≥ ρ i (Λ σ ) , ∀ i ∈ {2, ..., m} for Λ * the array of intervals computed in Algorithm 3. The computation of the "sensitivity radius" requires solving a single bottleneck assignment, and so has complexity O(B(n, m)) or O(n 2.5 ) with the same simplifications as previously discussed.

Conclusion
In this paper we propose two frameworks for assessing the sensitivity of a bottleneck assignment problem, as well as algorithms for the computation of the sensitivity within each framework. The analysis provided is driven primarily by the characterisation of "exclusive sets", and the connection of these sets to the bottleneck assignment problem. The combination of the theory of exclusive sets, along with recursive applications of the bottleneck assignment problem, allow for these algorithms to be run with off the shelf assignment solvers and a minimum of additional programming. The sensitivity analysis provided can be used to certify the optimality of a solution, if for example the true assignment weights can be shown to be contained by the provided intervals, or as a measure of the robustness of an assignment solution. Further research should concentrate on the expansion of this type of sensitivity analysis to other formulations of the assignment problem, as well as other formulations of the "largest" set of intervals besides the lexicographic ordering. P n×m \ P e * ⊆ ∪ e∈S e * P e , i.e., all assignments which do not include e * , assign at least one edge from S e * . Therefore, there is at least one edge within S e * which is assigned in Π ′ . However, as S e * satisfies (8), we conclude that Π ′ must contain an edge with weight greater than the weight of e * , which is a contradiction.

Appendix B. Proof of Theorem 1
We will prove this by showing that given Λ * = lexmax(L 0 ∩ L E ), we are able to construct an assignment Π and an exclusive set S e * that satisfy (7) and (8) over W = W + P , ∀ P ∈ Λ * . Therefore, we will have that Λ * ∈ A Π and Λ * ∈ X S e * . We will then show there exists no lexicographically larger Λ in L 0 ∩ X S e * ∩ A Π , completing the proof.
We begin by constructing two particular perturbations P 1 , P 2 ∈ R n×m , with P [e] the perturbation corresponding to the edge e, Every edge in P 1 is perturbed as negatively as possible, except e * , and the opposite in P 2 . By (5), we have that e * ∈ E(W +P ), ∀ P ∈ Λ * , including perturbations P 1 and P 2 . By Lemma 1, we have that there exists an assignment and an exclusive set satisfying (7)-(8) for each of the perturbations P 1 and P 2 . We let S e * be defined as the exclusive set satisfying (8) for W 1 := W +P 1 , and Π be defined as the assignment satisfying (7) for W 2 := W + P 2 . By the construction of perturbations P 1 and P 2 we have that (7)-(8) are satisfied by Π and S e * for all P ∈ Λ * , and thus Λ * ∈ A Π and Λ * ∈ X S e * . Therefore, To complete the proof, note that for any Λ ∈ L 0 ∩ X S e * ∩ A Π , we have e * ∈ E(W + P ), ∀ P ∈ Λ by Lemma 1. Therefore, which completes the proof. the provided bottleneck assignment and exclusive set. As the exclusive set is held fixed and so are the corresponding boundaries, we therefore focus on the boundaries corresponding to the edges in the bottleneck assignment Π in lines 6-9.
Algorithm 1 returns the the minimal magnitude bounds λ e * = λ e = w e * − w e 2 for e := argmax e∈ Π\{e * } w e . This bound is directly proportional to the difference w e * − w e , and as all bottleneck assignments by definition have maximal edge weight w e * , the bound is maximised by the assignment which minimises w e . Over all assignments, the lexicographic assignment minimises the second largest weight. Similarly, for all subsequent weights, we have that the lexicographic assignment minimises the i-th largest weight, and thus maximises the i-th largest bound λ e := w e * − λ e * − w e , and therefore Appendix E. Proof of Lemma 4 An exclusive set relative to an edge e * is defined by three properties, laid out in Definition 5. The set of edges returned from Algorithm 2 satisfies the first two properties from the definition trivially. To see that it satisfies the final property, note that each edge in the set S e * constructed in Algorithm 2 is as well as the bottleneck edge e * are assigned the weight ∞. The algorithm terminates when the bottleneck edge of the graph has weight ∞. Therefore, there are no assignments remaining in the graph which do not assign either the bottleneck edge e * or an edge in S e * , which is precisely the final property defining an exclusive set with respect to e * .
Next, we prove with S e * as an input, the output array of intervals Λ * of Algorithm 2 is the lexicographically largest set of allowable perturbations over all exclusive sets S e * ∈ S e * . Let Λ ′ be the lexicographically largest array of intervals which satisfies for some k ∈ {1, ..., nm − 1}. Note that, by Assumption 2, the bottleneck edge at every iteration of the while loop is unique, so for {e 1 , e 2 , ..., e k } the bottleneck edges from the first k iterations of the while loop in Algorithm 2, we have λ ′ e i = λ * e i . Assume that ρ k+1 (Λ ′ ) > ρ k+1 (Λ). There then exists an allowable perturbation such that w e + p e < w e * + p e * for some e ∈ S e * . Because e was returned in the k +1 iteration of the while loop in Algorithm 2, we know it is the maximal weight edge in some assignment Π, and therefore there exists a perturbation P under which all edges of Π would have weight less than e * , and thus P would not be allowable.

Appendix F. An Auxiliary Lemma
Lemma 5. The sequence of bounds determined within Algorithm 3 is nondecreasing.
Proof. The bound determined on the i-th iteration of Algorithm 3 is the minimum weight bottleneck edge over E(B e ), ∀ e ∈ Π. We therefore show that the sequence of bottleneck edges from each of these sets B e is nondecreasing, completing the proof of the lemma. Focusing on a single set B e for some e ∈ Π, we can separate the iterations into two cases: either the minimum weight bottleneck is from B e , or it is from some other set B e ′ corresponding to an edge e ′ ∈ Π, with e ′ = e.
In the first case, the minimum weight bottleneck edge is b = E(B e ) with weight w b . Assume, previous to the i-th iteration, we have λ e = ∞. Then for any edge e ′ satisfying B e [e ′ ] ≥ w b , we have that B e [e ′ ] is increased or remains constant after updating. The subsequent bottleneck edge of B e is drawn from this set, so the subsequent bottleneck edge weight is greater than or equal to w b . If instead we have λ e = ∞, then only w b is set to ∞, so the subsequent bottleneck edge weight from B e is greater than or equal to w b .
In the second case, the minimum weight bottleneck edge is b ′ = E(B ′ e ) with weight w b ′ . Therefore, we have that the weight w b ′ ≤ w b for w b the weight of b = E(B e ), as the bound is determined by the minimum of these bottleneck edge weights. By careful (tedious) examination of the update function, one may observe that if the update of the weight B e [b ′ ] results in a strict decrease then w b ′ > B e [b ′ ]. We therefore have that B e [b ′ ] < w b ′ ≤ w b , i.e. that the updated weight was less than the bottleneck edge weight of B e , and remained so after being updated, and therefore does not affect the bottleneck edge weight.

Appendix G. Proof of Theorem 2
First, to obtain a contradiction, we assume there exists an array of intervals Λ ′ ∈ L 0 ∩ L A which agrees with Λ * on the first k minimal magnitude bounds, i.e., ρ i (Λ ′ ) = ρ i (Λ * ), ∀ i ∈ {1, ..., }, but has a strictly greater k+1 minimal magnitude bound value, i.e. ρ k+1 (Λ * ) < ρ k+1 (Λ ′ ). We show that Λ ′ contains a perturbation P such that Π ∈ BAP(W + P ), which is a contradiction by the definition of L A . By Assumption 3, the bottleneck edges at each iteration of the Algorithm have been unique, so for B k = {λ * 1 , λ * 2 , ...} the bounds which have been set by the k − th iteration of Algorithm 3 we have λ ′ i = λ * i , ∀ λ * i ∈ B k . The bound ρ k+1 (Λ * ) is determined by a bottleneck assignment Π ′ = BAP(B e ) for some e ∈ Π, with e ∈ Π ′ . For each edge e ′ ∈ Π ′ , we have that whichever of λ e ′ , λ e have been undetermined by the k + 1-th iteration of Algorithm 3 will be greater than or equal to ρ k+1 (Λ * ), by Lemma 5. However, from the definition of each B e [e ′ ], there must then exist a perturbation P ∈ Λ ′ such that Π ′ contains all edges with weight strictly less Π. We therefore have that Π ∈ BAP(W + P ) for some P ∈ Λ ′ , and thus Λ ′ ∈ L A , which is a contradiction.
We have shown there exists no lexicographically larger array of intervals Λ ′ ∈ L A , however we have not yet shown that Λ * ∈ L A . In order to show this, we utilise the previously developed theory of exclusive sets. Algorithm 3 terminates when min e∈Π B e [b e ] = ∞. An edge weight e ′ of B e is defined to be ∞ only if e ′ = e, or e ′ − λ e ′ ≥ w e + λ e . Therefore, if min e∈Π B e [b e ] = ∞, we precisely have that there exists an exclusive set of edges S e such that Λ * ∈ L e , for L e defined in (10). However, with Λ * ∈ L e , ∀ e ∈ Π, we have that for every perturbation P ∈ Λ * there exists no assignment with all edges strictly less than any e ∈ Π, and therefore Π ∈ BAP(W + P ), ∀ P ∈ Λ * and Λ * ∈ L A .