{'fraction_non_alphanumeric': 0.037962209177771114, 'fraction_numerical': 0.00612708342259737, 'mean_word_length': 4.091623036649215, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Uncertainty Intervals for Robust Bottleneck Assignment

We examine the robustness of bottleneck assignment problems to perturbations in the assignment weights. We derive two algorithms that provide uncertainty bounds for robust assignment. We prove that the bottleneck assignment is guaranteed to be invariant to perturbations which lie within the provided bounds. We apply the method to an example of task assignment for a multi-agent system.


I. INTRODUCTION
This paper focuses on quantifying the set of weight perturbations which maintain the optimality of the original assignment. Task assignment is a central part of autonomous multi-agent systems, assigning agents to tasks in such a way as to optimize some measure of the quality of the assignment. We model the problem with a graph, with the agents and tasks as vertices and the assignments as weighted edges. The optimization cost can be any of minimum weight, minimum total weight, balanced weight, or one of many other types of assignment problems. In many scenarios, especially in physical applications, the weight of assigning an agent to a task has some associated uncertainty. This could be due to a physical measurement error such as a radar covariance, a dynamic environment within which the decisions are being made, or simply decimal roundoff errors. The optimal assignment is robust to some set of perturbations, and this paper provides a parameterization of that set of allowable perturbations for the bottleneck assignment problem.
This problem is studied under various names, such as "sensitivity" [1], "stability" [2], or "post-optimality" [3]. We use robustness to refer to the range of variations in the problem parameters under which we can certify the optimal solution. An overview of modern linear sensitivity analysis and its application is covered in [4]. In [4], they differentiate between several types of sensitivity analysis, focused on different aspects of the optimal solution such as optimal cost, active constraints, and the slope of the optimal cost function. The assignment problem, due to its additional constraint structure, is best approached using what is defined as "Type 2 Sensitivity Analysis". However, [4] focuses on perturbations of a single variable. We will use the term "robustness" to describe the effects of uncertainty in weight on all of the assignments.
In this paper we focus on the robustness of the bottleneck assignment problem (BAP). In a matching of agents to tasks, each with it's associated weight, the BAP seeks to minimize the maximum weight within a matching. In [5] the BAP to assign multiple decoys to multiple incoming threats. The bottleneck property minimizes the worst case time it takes each decoy to seduce and divert the threat away from the asset. This ensures that all threats are dealt with in the minimum time. The BAP is used in other minimum time applications,such as [6] where they give the example of transporting perishable goods or military supplies reaching command posts during an emergency.
An algorithm with robustness guarantees is provided in [7] along with several complexity improvements on others' work. However, this approach is used to find robust solutions, not to quantify the robustness of the optimal solution to the original problem. Robustness for the linear assignment problem to correlated perturbations in adjacent to a single node is examined in [1], reflecting an error in the state of an agent or a task. In [8], robustness/stability/sensitivity of the solution for the case where all perturbations are bounded by the same bound is established. This differs from the results of this paper where perturbation bounds are not uniform for all weights. Additionally, contrasting with [8], the algorithms for computing these bounds are presented.
Our contribution in this paper is finding individual perturbation bounds for each weight within which we certify the optimality of the original assignment solution. We allow all weights to vary independently and simultaneously, rather than restricting variations to a subset of the edges. In the presence of uncertainty, these bounds may provide sufficient robustness to certify that the assignment made was optimal. However, it may be that the assignments made are not robust enough for the user's needs. In this case, the algorithms proposed here can only alert the user to that fact, they do not propose a more robust assignment solution.
The paper is organized as follows. Section 2 is devoted to background on the assignment problem and a formal definition of robustness. Section 3 will provide the lower bounds for the bottleneck assignment problem, and the algorithms to find them. Section 4 covers numerical examples and implementation. Section 5 concludes and remarks on further analysis.

II. PROBLEM FORMULATION
Define a graph G = (V, E, W) over which we will solve the assignment problem. Let the set of vertices be V = V A ∪ V T such that V A ∩ V T = ∅ and |V A | ≤ |V T |, the edge set E ⊆ V A × V T , and edge weights W = {w ij ∈ R | (i, j) ∈ E}. We also define a set of binary decision variables variable {π ij | π ij ∈ {0, 1}, (i, j) ∈ E} to indicate if the edge from vertex i to j was assigned. With this graph and these decision variables, the bottleneck assignment problem can be formulated as If π ij = 1 then we say that vertex i is assigned to vertex j. In the rest of the paper the double indices associated with edge (i, j) ∈ E will be represented as a single index. Constraints (1b) and (1c) ensure that every vertex is assigned to at most one other vertex. Two edges are called adjacent if they share a common vertex. A matching in G is a set of pairwise non-adjacent edges. That is, no two edges share a common vertex. A maximum matching M in G is a matching with the largest number of edges. The bottleneck problem finds the maximum matching on the graph which minimizes the worst case edge weight. In this paper we focus on maximal cardinality bipartite matchings, where in at least one of the vertex sets V A all vertices are included in the matching. However, for brevity, we will refer to maximal cardinality bipartite matchings as maximal matchings.
The bottleneck assignment problem is well studied [9], and there are a many algorithms that solve it. The threshold algorithm, Algorithm 1 below, solves the bottleneck assignment problem [9], and provides intuition used later in the paper. The algorithm first sorts the edge set in descending according to their weights (line 1). If a maximum matching exists within the sorted edge set (line 3), then the edge with the greatest weight is removed (line 5). Checking for a maximum matching and removing the greatest weight edge is repeated until no maximum matching exists. The algorithm terminates with the last removed edge being the bottleneck edge. Algorithm 1 has complexity O(T (N )N ) where T (N ) is the complexity for checking the existence of a maximum matching in the set of edges |E| = N . The most common method is the Hopcroft-Karp Algorithm, which has complexity O(|E| |V|) [9]. There are faster probabilistic methods, see [9] for a survey of methods. This gives Algorithm 1 complexity O(N 2 |V|). Note that Algorithm 1 is given here only for intuition and context, the methods described below pertain only to the robustness analysis of the optimal solution. The actual algorithm used 4Ē ←Ē \ {e}; 5 end 6 return e \\ The bottleneck edge Algorithm 1: Threshold Algorithm for solving the BAP to find the bottleneck is irrelevant to our results.
To formally define robustness related to the bottleneck assignment problem, we first define the perturbed graph.
where w e ∈ W is the weight of edge e from the original graph and δ e ∈ D is some perturbation from a set of scalar perturbations D ⊆ R.
Define the mapping A(G) which takes a graph and returns the index of the bottleneck edge. If there are multiple equivalent bottleneck edges, then the mapping will the return the set of them.
Definition 2. Let e * ∈ A(G) be the bottleneck edge of the graph G. If e * ∈ A(Ḡ), for the perturbed weight graph in Definition 1, then the bottleneck assignment e * is robust to the set of perturbations {δ e | e ∈ E}.
With this definition of robustness, the problem can be stated as follows.
Problem. Find the set of allowable perturbations Λ such that the bottleneck assignment e * ∈ G is robust to the perturbation λ = {δ e | e ∈ E} if and only if λ ∈ Λ.
Remark. The parametrization of the set Λ as defined in the problem statement has tangible repercussions for task assignment under uncertainty. For example, suppose the graph represents a task assignment in a physical multi-agent system. The agents and tasks are the vertices, and the edges are the possible assignments of agents to tasks, each with an associated weight. If the uncertainties associated with the assignment weights fall within the set of allowable perturbations Λ, then the bottleneck assignment is guaranteed to remain optimal, preventing any need for reassignment.

III. ROBUSTNESS OF THE BOTTLENECK
To parametrize the set of allowable perturbations Λ, we first propose an optimization problem to find a subset where we have continued to use the graph notation presented in Definition 1.
To find Λ ∆ , we first define three bottleneck edges These are the bottleneck edges of the original graph G and of two subgraphs G − and G + . Define G − to be the graph constructed by removing the vertices, edges, and weights adjacent to and including e * and G + to be constructed by removing only the edge and weight e * , w e * from the original graph. The differences between the weights of these three bottleneck edges e − ,e * , and e + will bound the allowable perturbations, leading to the parameterization of Λ ∆ .
Lemma 1. Consider the indices e − ,e * , and e + , defined in (3) to (5). Then w e − ≤ w e * , and if e + exists then w e * ≤ w e + .
Proof. First we will prove that if e + exists, w e * ≤ w e + . By the definition of e * , there is no maximum matching on the original graph G composed of edges that all have weight less than w e * . Since w e + is an edge with the greatest weight in a maximum matching on the graph G + , which is missing the edge e * , w e + must be greater than or equal to w e * .
Next, to obtain a contradiction, assume w e − is greater than w e * . By the definition of e * , there exists a maximum matching on G with e * the greatest weight edge in that matching. Let π * ⊆ E represent the edges in that matching. The set π * \ {e * } ⊆ E − and is a maximum matching on G − . However, the edge with the greatest weight in π * \ {e * } has weight less than or equal to w e * , which contradicts w e − being greater than w e * .
Using the concept of the subgraphs G − and G + , we can bound ∆ from (2a), and construct Λ ∆ . Theorem 1. Let w e * be the weight of the bottleneck edge e * on the graph G, and let w e − , and w e + be the bottleneck weights of the subgraphs G − and G + , respectively, as defined in (3) to (5). The bottleneck assignment is robust, in the sense of Definition 2, to perturbations in Λ ∆ where In the case that the graph G + as defined in (5) does not have a maximal matching, the perturbations are bounded by Proof. We will prove by contradiction that no edge x with weight w x = w e * will be the bottleneck of the perturbed weight graph under some set of allowable perturbations.
Letw i = w e + δ e be weight of edge e after perturbation. Note that e * and e − guarantee the existence of a maximum matching with greatest weight w e * and second greatest weight w e − . Let π * be the set of edges corresponding to that maximum matching.
To obtain a contradiction, let the edge x = e * be the bottleneck of the perturbed weight graphḠ as in Definition 1, with perturbed weightw x =w e * .
We will first establish thatw x must be strictly less than w e * . By the definition of the bottleneck,w x is less than or equal to the greatest weight edge in every maximum matching on the perturbed weight graph. Therefore,w x is less than or equal to the greatest weight edge in the set π * . By Lemma 1 and the bound on the perturbations,w e * is the greatest weight edge in the matching π * . Therefore, w x <w e * . Additionally, becausew x is the bottleneck edge, it must be the greatest weight edge in a maximum matching π x , and thus each edge in π x must have a perturbed weight less thanw e * and clearly e * / ∈ π x .
We will now establish that sincew x <w e * , it cannot be the bottleneck edge. Because of the bound on the perturbations, the only edges which can be perturbed to have weight less thanw e * are those edges which have unperturbed weight w j < w e + . Therefore, every edge in the maximal matching π x must have an unperturbed weight less than w e + . However, by the definition of e + , there is no maximal matching composed of weights less than w e + that does not contain e * . Therefore, π x does not exist andw x cannot be the new bottleneck edge. Example 1. Consider a scenario where |V A | = |V T | = 3 and E = V A × V T . This could represent a physical scenario with a fully connected set of three agents and tasks. The weight set W is represented by a matrix C, where w ij is its ij-th element. This is a convenient representation and will be used for the rest of the paper. This matrix is termed the cost matrix and for this example is Algorithm 1 can be applied to this graph. The sorted list of weights is clearly the integers from 9 to 1, and initially there are six maximum matchings in this graph. Removing the greatest weight edge leaves 4 maximum matchings in the graph. Removing the greatest weight edge again leaves us with the graph whose corresponding cost matrix is where ∞ represents the absence of an edge.
Here if we were to remove the greatest weight edge there would be no maximum matchings available, so the edge with weight 7 is the bottleneck. We can now define the cost matrices of the two subgraphs G − and G + to be Running Algorithm 1 on these two subgraphs, we find e − and e + to be the edges with weight 4 and 8 respectively. In accordance with Lemma 1, w e − = 4 ≤ w e * = 7 ≤ w e + = 8.
Using (6), we find the ∆ value for this graph to be 1 2 . Therefore, the graph G is robust to any set of weight perturbations such that no perturbation has magnitude greater than or equal to 1 2 .
Equation (6) states that as long the perturbations are all within the interval [−∆, ∆], the optimal assignment remains unchanged. This results coincides with the result presented in [8]. However, by relaxing these constraints, allowing the intervals to be unique and asymmetric, we are able to expand this set of allowable perturbation intervals.
Note that in the proof for Theorem 1, the salient property of ∆ is that edges with weight w j ≥ w e + cannot be perturbed to have weightw j <w e * , and edges with weight w j ≤ w e − cannot be perturbed to have weightw j >w e * . However, this property can be maintained with larger and asymmetric bounds on the perturbations. Additionally, the edges which are between e − , e * , e + are irrelevant to the method, they do not change the bottleneck edge regardless of their weight. Therefore, for edges between e − and e + other than e * , we need not bound their perturbations at all. This leads us to Algorithm 2 below. Proposition 1. The bottleneck assignment is robust, in the sense of Definition 2, to the set of perturbations defined in Algorithm 2.
Proof. Let e − ,e * , and e + be defined as in (3) to (5), and let ∆ + and ∆ − be defined by Algorithm 2. Letw j represent the perturbed weight of edge j. Define the sets of upper and lower bounds returned by Algorithm 3 as U and L. Let (L j , U j ) represent the allowable perturbation for edge j, such thatw j − w j ∈ (L j , U j ).
If the bounds provided by Algorithm 2 guaranteew j ≥ w e * for any edge j with weight w j ≥ w e + , andw j ≤w e * for any edge j with weight w j ≤ w e − , then the proof for Theorem 1 applies to the set of bounds from Algorithm 2.
For any edge j with weight w j ≥ w e + , For any edge j with weight w j ≤ w e − , Data: (e * , G) 1 e − ← A(G − ) ; 2 e + ← A(G + ) ; 3 U \\ Upper bound on the allowable perturbations ; 4 L \\ Lower bound on the allowable perturbations ; Therefore, the perturbation intervals provided by Algorithm 2 have the same properties as those provided in Theorem 1, and the bottleneck assignment is robust to perturbations within the bounds provided by Algorithm 2.
Consider the case where an edge with weight greater than the bottleneck is subject to a positive perturbation, or a an edge with weight less than the bottleneck edge is subject to a negative perturbation. The bottleneck assignment is clearly robust to these types perturbations. This intuition provides additional insight into the set of allowable perturbations Λ.

Proposition 2.
Let w x be the weight of an edge x ∈ E,w x be the perturbed weight of that edge, and e * ∈ E be the bottleneck as defined in (4). The bottleneck assignment is robust, in the sense of Definition 2, to any perturbations for whichw x >w e * iff w x > w e * , andw x <w e * iff w x < w e * for all x ∈ E.
Proof. Let G be the set of all edges with weights greater than the bottleneck edge e * , and L the set of all edges with weights less than the bottleneck edge e * . By the definition of the bottleneck edge, there is guaranteed to be a maximum matching with all edges in the set {L∪e * }, and no maximum matching with all edges in the set L. By the definition of the set G, the maximum matching of edges from the set {L ∪ e * } will all have lower weights than any edges in the set G. Thus, every edge in the set G is excluded from being the bottleneck. Therefore, the ordering of the edges within the sets G and L has no impact on the bottleneck.
Remark. Proposition 2 demonstrates that the allowable perturbations on all edges with weight greater than the bottleneck are unbounded above, and the allowable perturbations on all edges with weights less than the bottleneck are unbounded below. In light of this, we will refer to the allowable perturbation sets as half space constraints, because they will only specify an upper or lower bound with the other bound being negative or positive infinity.
Finally, note that the method for constructing the set Λ ∆ and the subsequent expansion of the allowable perturbation intervals has nearly the order computational complexity as the BAP, because it involves solving the bottleneck assignment problem on two subgraphs. One of these subgraphs, G + , is only one edge smaller than the original. However, by using only Proposition 2, we can construct a different set of allowable perturbation intervals, as shown in Algorithm 3.
Data: (e * , W) 1 U \\ Upper bound on the allowable perturbations ; 2 L \\ Lower bound on the allowable perturbations ; Proof. Define w x to be the weight of an edge x ∈ E,w x to be the perturbed weight of that edge, and e * ∈ E be the bottleneck edge as defined in (4). Define the sets of upper and lower bounds returned by Algorithm 3 as U and L. Let (L j , U j ) represent the allowable perturbation for edge j, such thatw j − w j ∈ (L j , U j ).
Let G be the set of edges with weights greater than the bottleneck, and L the set of edges with weight less than the bottleneck. According to Proposition 2, if these sets are unchanged by the perturbation then the bottleneck assignment is robust to that perturbation. Let w j > w e * be the weight of an edge in set G, Therefore,w j >w e * for all elements of G, so G is unchanged by the perturbation. Let w j < w e * be the weight of an edge in set L, Therefore,w j <w e * for all elements of L, so L is unchanged by the perturbation.G and L are unchanged by the perturbation, so the bottleneck assignment is robust to this set of perturbations.
Algorithm 3 constructs these bounds by performing one pass through the weight set to find the minimum distance weight to the bottleneck, and another pass through the edges to construct their upper and lower bounds. Therefore, it has complexity O(|E|).

IV. NUMERICAL EXAMPLE
First, to illustrate the various bounds, extensions, and applications, we will analyze a small example. Consider a fully connected multi-agent system with 3 agents and 4 tasks with cost matrix Running the bottleneck algorithm on the two subgraphs gives e − = (3, 2) with weight w e − = 12.1 and e + = (2, 4) with weight w e + = 28.3. To find the set of allowable perturbation intervals we first use Algorithm 2, because we have already identified e − , e * , and e + . The results are presented in Table I. Next, we compare the allowable perturbation intervals from running Algorithm 3 over the same graph. The results are presented in Table II Note that for some edges Algorithm 3 and Algorithm 2 provide the same bounds. However, the smallest intervals are larger using Algorithm 2. Some edges are also entirely unbounded using Algorithm 2.
In both algorithms edges above the bottleneck can be infinitely positively perturbed, and edges below the bottleneck can be likewise infinitely negatively perturbed. Therefore, to compare the algorithms, we propose examining the magnitude of allowable perturbation in the non-infinite direction. However, note that this method does not capture the number of unbounded edges from Algorithm 2. Fig. 1 presents simulation results. The graphs generated have |V A | = |V T | = [3,100] nodes and are fully connected E = V A × V T . The plots show the minimum magnitude allowable perturbation, or the "tightest" allowable perturbation bound. For each graph size from [3,100] we randomly generated 1000 graphs with weights randomly sampled from [0, 100]. Algorithm 2 is provides a larger minimum size intervals as the problem size grows. The minimum robustness of Algorithm 3 is driven entirely by the density of the weights, and the larger the problems the more likely there are many weights near the bottleneck. However, Algorithm 2's minimums also drop as the problem size grows larger, because its performance is tied to the density of the greatest weight edges in the maximum matchings, which will also increase with the number of tasks in the graph.

V. CONCLUDING REMARKS
In this paper the robustness of the bottleneck assignment problem (BAP) to a set of perturbations is analyzed. Two methods of approximating the set of allowable perturbations are proposed, one with the same order computational complexity as the BAP, and the other is linear in the number of edges in the graph. These approaches differ from the previous approaches in literature by allowing all weights to vary simultaneously and independently. Simulations showed that the higher order complexity bound provided better worst case robustness. The robustness of the graph can be used to guarantee the optimality of the bottleneck assignment if the errors in each weight fall within the set of allowable perturbations.
In future work, similar robustness for the linear assignment problem, the general assignment problem, and various other assignment problem formulations will be investigated. Another possible future problem would be examining the geometric implications of these robustness intervals, perhaps informing a method of deploying multi-agent system in a pattern likely to lead to robust solutions.