Investigating tolerance of uncertainty, COVID-19 concern, and compliance with recommended behavior in four countries: The moderating role of mindfulness, trust in scientists, and power distance

Consumers' compliance with recommended behavior during the COVID-19 pandemic helps contain the spread of the virus and positively impacts marketplace outcomes. This study investigates the effect of consumers' tolerance of uncertainty on COVID-19 concern, compliance with recommended behavior, and panic buying intentions, across four countries (Germany and USA with a low power distance index; India and The Philippines with a high power distance index; N = 1272). We test the moderating role of power distance, mindfulness, and trust in scientists, among these relationships. Our results show that tolerance of uncertainty is negatively associated with COVID-19 concern, and COVID-19 concern is positively associated with compliance and panic buying intentions. In high power distance countries, tolerance of uncertainty is negatively associated with compliance. The negative association of tolerance of uncertainty with COVID-19 concern is more pronounced at low levels of mindfulness, and consumers with high COVID-19 concern and high trust in scientists demonstrated the highest compliance. Our findings reveal that stressing the importance of mindfulness, though positive overall, might not yield more compliance. Interventions to make consumers more concerned about the consequences of the pandemic and, at the same time, enhancing their trust in scientists, can lead to higher levels of compliance.

Introduction
As countries around the world grapple with the third or fourth waves of the COVID-19 pandemic, most countries are continuing to apply strict measures to contain its spread, including social distancing, quarantining, wearing masks and lockdowns (Van Bavel et al., 2020). However, individuals' perceived inconveniences, discomfort or lack of concern has led to decreased compliance in many countries (Stosic et al., 2021). Indeed, individuals' compliance with recommended behavior during the COVID-19 pandemic helps contain the spread of the virus and is positively associated with consumer and marketplace outcomes (McKinsey & Company, 2020).
Given that individuals' adherence is the key factor in the effectiveness of these measures (Fragkaki et al., 2021), compliance with recommended behavior is a variable of great importance to scholars and practitioners during the pandemic. However, "little is known about what distinguishes those who comply from those who do not" (Zhang et al., 2021, p. 168). This has led to an urgent call for research by several scholars to understand individual differences that lead to differences in pandemicrelated intentions and behaviors (Fragkaki et al., 2021;Stosic et al., 2021;Van Bavel et al., 2020). In answering this call, our research aims to investigate what makes consumers more or less concerned about COVID-19, given that consumers' concern is a key variable to understand their compliance (Kwon et al., 2021). Apart from consumers' COVID concern and compliance with recommended behavior, our research also examines consumers' panic buying intentions.
Building on extant research, we develop and empirically test a conceptual model of consumers' individual differences (tolerance of uncertainty, mindfulness, trust in scientists), associated with COVID-19 concern, compliance with recommended behavior, and their panic buying intentions. Further, there has been much interest in differences in citizens' compliance with recommended behavior across countries. Our theorizing includes power distance, a cultural difference variable (Hofstede et al., 2010). We test our model using a sample from four countries, two of them with a low power distance index (Germany and USA) and two of them with a high power distance index (India and The Philippines).

Tolerance of uncertainty, COVID-19 concern, and compliance with recommended behaviors
Tolerance of uncertainty (TU) is an individual difference in tendency to consider the possibility that something negative happens in the future as unacceptable (Carleton et al., 2007). TU is related to trait anxiety, anxiety disorders, and worry; individuals who are low in TU are more vulnerable to these conditions (Leyro et al., 2011). People low in TU also feel lonelier during the COVID-19 pandemic (Parlapani et al., 2020), show less resilience (Karataş & Tagay, 2021), and fear COVID-19 more (Deniz, 2021). In turn, fearing COVID-19 positively influences individuals' preventative behaviors in response to the pandemic (Jovančević & Milićević, 2020). Indeed, lack of concern about COVID-19 has been implicated in decreased compliance with recommended behavior (Stosic et al., 2021). Based on these studies, we postulate a mediation hypothesis wherein TU is negatively associated with consumers' concern about COVID-19, and COVID-19 concern, in turn, is positively associated with compliance with recommended behavior (H1).

Panic buying intentions
Since the beginning of the pandemic, many consumers have engaged in panic buying behavior, which is quite common during disasters (Dholakia, 2020). People might panic buy during the pandemic due to different reasons: as a response to fear, as a means to restore lost control over the environments, because of the perceived scarcity of goods, and as a result of social learning effects based on shared concerns (Arafat et al., 2020). In this research, we focus on the role of TU and COVID-19 concern on consumers' panic buying intentions during the pandemic. Extant literature shows that consumers tend to engage in panic buying of groceries when they are concerned about food scarcity during a pandemic (Jovančević & Milićević, 2020), and that low TU is associated with hoarding symptoms (Mathes et al., 2017). Based on these findings, we postulate a mediation hypothesis, similar to the one on compliance with recommended behavior; TU is negatively associated with consumers' concern about COVID-19, and COVID-19 concern, in turn, is positively associated with panic buying intentions (H2).

The moderating role of mindfulness
Mindfulness is "one's complete attention to the experiences occurring in the present moment, in a nonjudgmental or accepting way" (Baer et al., 2006, p. 27). It is related to several psychological benefits such as positive emotional states, enhanced self-regulation (Brown & Ryan, 2003), and improved coping with stressful waiting periods (Sweeny & Howell, 2017). Recent research has shown multiple benefits of being mindful during the pandemic. Mindful consumers show more savoring, i.e. they notice positive aspects in changes that occurred because of COVID-19 (Götmann & Bechtoldt, 2021). Mindfulness is also associated with lower levels of boredom and higher levels of life satisfaction during the lockdown because mindful people have higher awareness and use autonomous self-regulation strategies (Waterschoot et al., 2021). It is also related to decreased fear of COVID-19 . Based on findings that mindfulness helps individuals to stay in the "present" and have increased non-judgmental awareness (Baer et al., 2006), and that high TU leads to better coping with the uncertainty of the "future" (Carleton et al., 2007), we propose that their interaction will be positively associated with consumers' concern about COVID-19. In particular, we postulate that at lower levels of mindfulness, the negative association of TU with COVID-19 concern is more pronounced than at higher levels of mindfulness (H3).

The moderating role of trust in scientists
Trusting scientists might help to attenuate some negative consequences of COVID-19 concern. For instance, Plohl and Musil (2021) find that individuals who trust in science show a higher willingness to comply with COVID-19 prevention guidelines than those who don't. Believing in science also predicts believing in the effectiveness of wearing masks during the COVID pandemic, which in turn increases people's willingness to wear a mask in public (Stosic et al., 2021). We thus hypothesize that trust in scientists moderates the effect of COVID-19 concern on consumers' compliance with COVID-19 prevention measures, such that consumers with high trust in scientists and high COVID-19 concern exhibit the highest compliance, and those with lower trust in scientists and lower COVID-19 concern exhibit the lowest compliance (H4). In addition, lower knowledge of science and lower levels of trust in medicine predict unreasonable behaviors during the pandemic, such as increased levels of consumers' panic buying behavior (Sailer et al., 2020). Hence, we predict that higher levels of trust in scientists and lower levels of COVID-19 concern will be associated with the lowest levels of panic buying behavior, while lower levels of trust in scientists and higher levels of COVID-19 concern will be associated with increased panic buying behavior (H5).

The moderating role of power distance
Power distance is a cultural dimension that refers to the extent to which individuals expect and accept the situation where power is distributed unequally between the society members (Hofstede et al., 2010). Countries and cultures can differ on this dimension. Within a culture, individual differences in people's beliefs about power inequality in society exist as well and can be measured as power distance beliefs (PDBs) (Yoo et al., 2011).
Based on recent research, we speculate that a country's power distance might be related to individuals' willingness to comply with COVID-19 recommended behavior. Cultures with low power distance rely on mutual obligation and generally do what authorities ask, thus, people might be more willing to comply with prevention measures. In contrast, in high power distance cultures, governments are more likely to force rules, which can lead to social protest (Hofstede, 2020, April 8). Furthermore, power distance has been shown to affect consumers' prosocial behavior such as donating money (Winterich & Zhang, 2014), such that consumers from high power distance cultures are less involved in charitable behavior. The same effect holds on the individual level: those with high PDBs show lower perceived responsibility to help others, which leads to decreased charitable giving. Apart from social responsibility to aid others, low PDBs lead to heightened empathy for victims of companies' poor labor practices (Xu et al., 2021).
We consider adhering to prevention measures during the pandemic not only as a form of self-protection but also as a specific form of prosocial behavior. Karić and Međedović (2021) show that caring about saving people's lives is positively associated with engagement in COVID-19 precautionary behaviors. Based on our first hypothesis about the indirect effect of TU on compliance with recommended behavior, and extant research on power distance and prosocial behavior, we postulate that TU and power distance interact to affect consumers' compliance with recommended behavior (H6). In particular, we expect that in high power distance cultures, tolerance of uncertainty negatively influences people's willingness to comply with COVID-19 recommended behavior (H6a). Extant research shows that high power distance leads to less prosocial behavior. Similarly, high power distance countries, unlike low power distance ones, do not have unwritten social obligations, and thus their inhabitants might not be motivated to stick to the COVID-related rules to protect other citizens. Thus, in high power distance cultures, when one's tolerance of uncertainty is low, a person will show increased compliance with preventative measures due to potentially heightened concern about the pandemic and as a means to protect themselves from COVID-19 uncertainty, not as a prosocial act. At the same time, we expect that in low power distance cultures tolerance of uncertainty does not affect people's willingness to comply with COVID-19 measures (H6b). In this case, a person will show high levels of compliance with preventative measures regardless of their tolerance of uncertainty, which might be driven by their social responsibility to protect others, which is more common in low power distance cultures. We do not hypothesize a similar interaction effect of TU and power distance on consumers' panic buying intentions. We believe that prosocial considerations in low power distance cultures are relevant for compliance with recommended behavior and not for panic buying intentions, since complying with recommended behavior during the pandemic includes elements of social distancing and keeping others safe along with oneself.
Two conceptual figures, based on our hypotheses about the indirect effect of TU on compliance with recommended behavior, via COVID-19 concern, and the moderating effects of mindfulness, trust in scientists, and power distance, are shown in Figs. 1 and 2.

Participants and procedure
One thousand two hundred and seventy-two respondents from four countries, Germany (N = 307; 40% female; Mean Age = 32), USA (N = 287; 50% female; Mean Age = 36), India (N = 340; 51% female; Mean Age = 38) and The Philippines (N = 338; 58% female; Mean Age = 34) were recruited on two well-known market research panels, Prolific (Germany and USA) and Pollfish (India and The Philippines). All participants were older than 25 years Participants responded to an online questionnaire with measures of study variables, and were each paid 3 USD, on average, for their participation.

Tolerance of uncertainty
The 12-items scale by Carleton et al. (2007) was used to measure respondents' intolerance of uncertainty. The items were then reversed coded to measure TU. As proposed by Carleton et al. (2007), an aggregate score of the 12 items was calculated to measure the TU construct (α = 0.91).

Mindfulness
The 15-items Mindfulness Attention Awareness Scale (MAAS) by Brown and Ryan (2003) was used to measure respondents' mindfulness.
Following Brown and Ryan (2003), an aggregate score of the 15 items was calculated (α = 0.96).

Power distance
We coded respondents from India and The Philippines as high power distance (High Power Distance = 2), and those from Germany and the USA as low power distance (Low Power Distance = 1). We also measured respondents' PDBs using a 5-item scale (α = 0.93) (Yoo et al., 2011).

Trust in scientists
We measured respondents' trust in scientists with a single question (I trust information from scientists who are working on COVID-19), on a 7point scale (from 1 = "strongly disagree" to 7 = "strongly agree").

Compliance with recommended behavior
Respondents' compliance with recommended behavior was measured with a 5-item scale (e.g., I intend to follow social distancing rules; I plan to wear a mask in public spaces). They expressed their agreement with these statements on a 7-point scale (from 1 = "strongly disagree" to 7 = "strongly agree"). The items were averaged (α = 0.82).

Panic buying intentions
We measured panic buying intentions with a 3-item scale (e.g., I intend to buy more than usual quantities of home essentials such as toilet paper, hand soap, and hand sanitizers to be on the safe side). Respondents expressed their agreement with these statements on a 7-point scale (from 1 = "strongly disagree" to 7 = "strongly agree"). The items were averaged (α = 0.93).
The scale items for the following measures -COVID-19 concern, trust in scientists, compliance with recommended behavior, and panic buying intentions -were developed for this study and were not piloted. Scale items employed to measure all study variables are listed in Table A1 in the supplemental document (Appendix A).

Power analysis
A sensitivity power analysis conducted on GPower 3.1 (Faul et al., 2009) revealed that 92 participants would yield 80% power to detect a medium effect (Cohen's f = 0.15; assuming α = 0.05), and 674 to detect a small effect (Cohen's f = 0.02; assuming α = 0.05). Hence, our sample size is adequate. We acknowledge that post-hoc power analysis has limitations and might lead to misleading conclusions because of the issues arising from a monotone function of the p-value (Dziak et al., 2020). statistics for the study variables by country, including mean comparisons.
We now report the individual moderation effects in our model. As predicted in H3, we found a significant interaction effect of TU and mindfulness on COVID-19 concern, F(1271, 1) = 14.736; p < 0.01. To interpret the interaction, we plotted the Johnson-Neyman points for mindfulness. Results showed that the lower the consumers' TU, the higher their COVID-19 concern, and that mindfulness moderates this relationship such that the effect of TU on COVID-19 concern is more pronounced at low levels of mindfulness ( As hypothesized in H4, we found a significant moderation effect of trust in scientists on the relationship between COVID-19 concern and compliance with recommended behavior, F(1271, 1) = 16.11; p < 0.01. To interpret the moderation, we examined the Johnson-Neyman points for trust in scientists. Consumers with higher (vs. lower) levels of trust in scientists showed higher compliance with recommended behavior at all levels of COVID-19 concern. Results showed that higher levels of COVID-19 concern (point estimate = 6.57) and higher levels of trust in scientists (point estimate = 7.0) were associated with the highest levels of compliance (point estimate = 6.59), whereas lower levels of COVID-19 concern (point estimate = 3.56) and lower levels of trust in scientists (point estimate = 4.46) were associated with lower compliance (point estimate = 5.34). Consumers' compliance was relatively high (point estimate = 6.18) even at lower level of COVID-19 concern (point estimate = 3.56) when trust in scientists was high (point estimate = 7.0).
Additionally, as predicted in H5, we found a significant moderation effect of trust in scientists on the relationship between COVID-19 concern and panic buying, F(1271, 1) = 5.02; p < 0.05. An examination of the Johnson-Neyman points showed that lower levels of COVID-19 concern (point estimate = 3.57) and higher levels of trust in scientists (point estimate = 7.0) were associated with the lowest levels of panic buying behavior (point estimate = 3.23), while higher levels of COVID-19 concern (point estimate =6.57) and lower levels of trust in scientists (point estimate = 4.46) were associated with the highest levels of panic buying behavior (point estimate = 5.33).

Implications
In this research, we investigated the indirect effect of consumers' TU on their compliance with recommended behavior, and their panic buying intentions. Consumers' COVID-19 concern mediated these relationships. Additionally, we examined the moderating role of consumers' mindfulness, trust in scientists, and power distance. We found that consumers' concern about COVID-19 mediated the relationship between TU and their compliance with recommended behavior and panic buying intentions (H1; H2). Further, results showed that power distance moderated the relationship between tolerance of uncertainty and compliance, such that in high power distance countries, tolerance of uncertainty is negatively associated with compliance (H6). Further, mindfulness moderated the relationship between tolerance of uncertainty and concern about COVID-19, such that among participants with lower levels of uncertainty, those who also had low levels of mindfulness showed lower levels of COVID-19 concern (H3). Finally, trust in scientists moderated the relationships between concern about COVID-19 and compliance, and concern about COVID-19 and panic buying behavior, such that those with high trust in scientists and high COVID-19 concern demonstrated the highest compliance, and those with low trust in scientists and high COVID-19 concern showed the highest levels of panic buying (H4; H5). We substantially extend recent research on the effect of TU on COVID-19 related concerns and behavior (Deniz, 2021;Satici et al., 2020) by investigating variables relevant to consumer behavior, and by theorizing about power distance. To our knowledge, power distance, a cultural variable, has not been studied in the context of other individual difference variables and COVID-19 related behavior.

Limitations and future research
Despite the theoretical and practical importance of this research, it is not without limitations. First, our cross-sectional survey research does not establish causality. Future research should use experiments to determine causal relationships in our conceptual model. Second, we only included four countries in our sample. A greater range of countries that vary on the power distance index can further validate our model and theorizing about the moderating role of power distance. Yet another limitation is that there are countries where the effect of the pandemic on consumers was significantly worse (e.g., Brazil), or significantly better (e.g., New Zealand). Future research can investigate the effect of the severity of the pandemic, and consumers' perception of their government's response to the pandemic, as additional variables that might affect the relationships in our conceptual model.

Conclusion
Based on our findings, stressing the importance of mindfulness, though positive in general, might not yield more compliance with recommended behavior when compared to enhancing consumers' trust in scientists. Interventions to make consumers more concerned about the consequences of the pandemic and, at the same time, enhancing their trust in scientists, can lead to higher levels of compliance. In addition, tolerance to uncertainty is a quality that can be changed (Deniz, 2021). Hence, interventions focused on helping consumers with very high levels of tolerance of uncertainty become more concerned about the adverse effects of the pandemic, could be developed and implemented to reduce the spread of the COVID-19 globally. In sum, our findings provide multiple insights for researchers and decision makers to be better equipped in handling future crises where adherence to recommended behavior could be key for economic and social recovery.

Ethical statement
All procedures performed in studies involving human participants were in accordance with the ethical standards and with the Helsinki Declaration and its later amendments or comparable ethical standards. Informed consent was obtained from all individual participants included in the study.

Funding disclosure
This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors. 4. I tend not to notice feelings of physical tension or discomfort until they really grab my attention. 5. I forget a person's name almost as soon as I've been told it for the first time. 6. It seems I am "running on automatic" without much awareness of what I'm doing. 7. I rush through activities without being really attentive to them. 8. I get so focused on the goal I want to achieve that I lose touch with what I am doing right now to get there. 9. I do jobs or tasks automatically, without being aware of what I'm doing. 10. I find myself listening to someone with one ear, doing something else at the same time. 11. I drive places on "automatic pilot" and then wonder why I went there. 12. I find myself preoccupied with the future or the past. 13. I find myself doing things without paying attention. 14. I snack without being aware that I'm eating. Trust in Scientists I trust information from scientists who are working with COVID-19 Compliance with recommended behavior 0.82 1. I intend to adhere to quarantine appeals. 2. I plan to improve my hygiene habits like hand washing and avoiding face touching. 3. I intend to follow social distancing rules. 4. I plan to wear a mask in public spaces. 5. I plan to avoid hosting or attending indoor and house parties. Panic buying intentions 0.93 1. I intend to buy more than usual quantities of food essentials such as milk, bread/rice/flour, butter/oil, etc. to be on the safe side. 2. I intend to buy more than usual quantities of home essentials such as toilet paper, hand soap, and hand sanitizers to be on the safe side. 3. In general, I plan to buy more supplies than usual in these times of the COVID-19 crisis.


The impact of COVID-19 on research within the homeless services sector

Purpose – This paper aims to discuss the challenges of conducting research with homelessness services frontline workersduring theCOVID-19pandemic. Design/methodology/approach – Between 2015 and 2019, the research team surveyed frontline staff in three cities about their psychosocial stressors and needs. In 2020, the authors replicated the previous study and expanded data collection to seven cities across Canada to determine the extent to which the COVID-19 pandemic impacted the well-being of frontline staff. This report describes how the authors adapted the research methodologies to continue work throughout the pandemic, despite various restrictions. Findings – The original studies had very high participation rates because of several methodological approaches that minimized barriers, especially in-person data collection. During the pandemic, distancing requirements precluded replicationof these same methods. Research strategies that enabled staff participation during working hours, with designated time allotted for participation, was key for ensuring high participation rates, as access to technology, availability of free time and other factors frequently make online survey research a hardship for these staff. Restrictive interpretation and regional variations of COVID-19 guidelines by some research ethics boards were also a challenge to rapid and responsive datacollection. Originality/value – Few studies describe the experiences of frontline workers in the homelessness sector, and quantitative reports of their experiences are particularly scant. Consequently, little is known about specific methodologies that facilitate large-scale data collection in the homelessness services sector. The present research advances the field by providing lessons learned about best practice approaches in pre and post COVID-19 front line worker contexts. A strength of this research is the well-controlled design. The authors collected data within several of the organizations that had previously participated. This fortunate baseline provided opportunity for comparison before and during the pandemic; the authors can highlight factors that might have had influence during the pandemic. describe implementation challenges and solutions to studying large populations homelessness frontline an illustrative example from a six-year, longitudinal study homelessness sector frontline

Findings -The original studies had very high participation rates because of several methodological approaches that minimized barriers, especially in-person data collection. During the pandemic, distancing requirements precluded replication of these same methods. Research strategies that enabled staff participation during working hours, with designated time allotted for participation, was key for ensuring high participation rates, as access to technology, availability of free time and other factors frequently make online survey research a hardship for these staff. Restrictive interpretation and regional variations of COVID-19 guidelines by some research ethics boards were also a challenge to rapid and responsive data collection.
Originality/value -Few studies describe the experiences of frontline workers in the homelessness sector, and quantitative reports of their experiences are particularly scant. Consequently, little is known about specific methodologies that facilitate large-scale data collection in the homelessness services sector. The present research advances the field by providing lessons learned about best practice approaches in pre and post COVID-19 front line worker contexts. A strength of this research is the well-controlled design. The authors collected data within several of the organizations that had previously participated. This fortunate baseline provided opportunity for comparison before and during the pandemic; the authors can highlight factors that might have had influence during the pandemic.
Keywords Frontline workers, Homelessness services, Pandemic research, Traumatic stress Paper type Research paper C onducting research on frontline homelessness sector workers has always been challenging. Staff are busy, stressed and not compensated well for their care and commitment. Workers may also prioritize client care above all other tasks. Research with this critical and difficult-to-access population has shed light on best practices in the field (Schiff and Lane, 2019). During the COVID-19 pandemic, however, researchers had to quickly pivot and adapt to changes in the worker population, their working conditions and the narrowing conditions under which we could conduct research. The purpose of this paper is to describe implementation challenges and solutions to studying large populations of homelessness sector frontline workers before and during the COVID-19 pandemic and beyond. To do this, we provide an illustrative example from a six-year, longitudinal study of homelessness sector frontline workers in seven cities across Canada.
(Information about the authors can be found at the end of this article.) The discourse on research infrequently focuses on implementation challenges. Furthermore, research on burnout, primary and secondary traumatic stress has often been impacted by recruitment issues and low responses rates (Schiff and Lane, 2019). Because of the COVID-19 pandemic, our team was presented with the unique opportunity to re-survey homelessness sector frontline staff working in pandemic conditions, who we had also surveyed prior to the pandemic, and measure the extent to which stressors created by the pandemic were affecting staff well-being. These additional stressors included ongoing threats of exposure to COVID-19 and increased demands from clients who feared contamination in shelters and client resistance to social isolation requests. While prior work had allowed us to identify challenges and opportunities specific to research in the field, the pandemic exacerbated these issues by making it even more difficult to reach and engage all staff. The lessons learned have broader implications for other field research.

Background
In both Canada and the USA, shelters are identified as high-risk work environments for multiple reasons: clients stay in crowded conditions with limited sanitation and live with multiple physical and behavioral (mental and addiction) issues that make them vulnerable to infectious disease (Buccieri and Schiff, 2016;Hwang and Burns, 2014). A scoping review of studies on staff burden in both Europe and North America found few studies that examine this population. This review suggested that staff in most countries are often untrained and illprepared for this work (Olivet et al., 2010;Schiff and Lane, 2019;Wirth et al., 2019). Emerging evidence suggests that frontline workers experience elevated risk of psychological injury from the stress of traumatic events experienced on the job (e.g. physical violence, suicide and overdose) (Schiff and Lane, 2019), and few organizations have implemented adequate trauma-informed practices (Waegemakers Schiff, 2019a). The significant increased risk of COVID-19 exposure adds to that stress. To develop policies that improve conditions for clients while protecting and enhancing worker safety, studies are needed that describe frontline homelessness sector workplace stresses, before and after COVID-19.
Homelessness sector frontline workers and workplaces: a study of pandemic preparedness in Canadian cities prompted by the alarm SARS viral outbreak in 2004, found that municipal governments, homeless organizations and staff in shelters were unprepared for the unique demands of those who could not "shelter in place" or practice preventative hygiene and physical distancing. Clients perceived staff as ill-informed on protocols for safety and how best to respond to client requests for accurate information about personal safety practices (Waegemakers Schiff and Lane, 2016b). Most of the learnings from that study failed to find traction among service providers who had neither the resources nor the initiative to develop comprehensive emergency plans beyond those for natural disasters, fires and floods. Resultantly, many organizations and municipalities did not have a comprehensive plan in place to inform homelessness sector staff of safety and protocols, in the event of a pandemic when the COVID-19 pandemic became a Canadian reality in March 2020.
From prior work, we know that when homeless services have not been prepared to address a pandemic, the resultant stress on staff can be enormous (Brown and O'Brien, 1998;Buccieri and Schiff, 2016;Waegemakers Schiff, 2019b). And there is limited information on how to support homeless sector frontline workers when workplace traumas occur (Olivet et al., 2010;Purtle, 2018;Wirth et al., 2019).
Prior to the COVID-19 outbreak, organizations providing homelessness services were ill-prepared to mitigate staff risk in high stress and traumatizing environments and the impact on staff was detrimental to their mental health and the services they delivered (Schiff and Lane, 2019;Waegemakers Schiff and Lane, 2016a). In the COVID-19 research project, we surveyed staff and added focused interviews with key administrators from organizations serving the homeless. Preliminary results confirm workers have faced additional work-related stressors and potential traumatizing situations in the workplace, including increased deaths from the virus, opioid overdoses and prolonged exposure to cold weather by many who prefer outdoor encampments to crowded indoor shelters.
Stress is socially contagious and readily transmitted among staff and clients (Dimitroff et al., 2017;Richter-Levin and Sandi, 2021) but is reduced by the presence of physical and psychological safety in the workplace. The COVID-19 pandemic has heightened concerns over lack of safety in homelessness sector programs as clients continue to be served in at-capacity shelters with large numbers of people forced to stay in close proximity, rendering physical distancing an impossibility. As well, proven hygiene options such as hand-washing and wearing protective masks and other personal protective equipment were initially hard to access. A correlate of increased workplace stressors is the high rates of sick leave and stress-related disability as reported by many organizations during key interviews with administrators. Furthermore, there are well-known workforce shortages of qualified, experienced frontline staff (Schiff and Lane, 2019). As a result, those who fall ill or require stress leave cannot readily be replaced, leading to a worsening care crisis for the remaining staff and their clients. Psychological trauma is highly impactful to victims and costly to organizations in terms of loss of productivity and prolonged stress leave (Milligan-Saville et al., 2017). The stressors specifically implicated by homeless sector staff have recently come to attention, as reports indicate rates of traumatic stress indicative of PTSD that are twice as high as other emergency services workers (Waegemakers Schiff, 2019b). The pandemic provided an opportunity to assess the extent to which staff stress had increased and which mitigating strategies might reduce this burden. However, recruitment and data collection strategies had to be modified to meet constantly evolving and locally divergent COVID-19 restrictions. Overall, we were concerned that participation rate, which had been strength of our previous research, would be diminished and the quality of survey responses would also be negatively affected.

Evolving methods for a dynamic research environment
Currently, we are conducting a study to examine work-related psychological injuries among homeless services frontline staff (HSFW) during the COVID-19 pandemic. The primary goal of the project is to understand the extent to which the COVID-19 pandemic impacted their psychological well-being and work-related disability. Study data derives from interviews and surveys from participating organizations across Canada and administrative data from the Alberta Workers Compensation Board (A-WCB). The findings aim to help organizations prioritize HSFW access to mental health services targeted trainings and other supports that would directly address their needs. An unanticipated consequence of the work has been an emerging understanding of the ways in which study protocols would need to be modified to maintain high rates of HSFW participation in the face of a changing and increasingly psychologically and physically dangerous working environment.
Research design: pre-and post-COVID-19: a major limitation of previous research on staff stress and burnout has been its reliance on convenience samples rather than populationwide groups. In a meta-analysis of STS, VC and burnout, Cieslak et al. (2014) noted that all reports consisted of convenience samples and most used online or mail in surveys, with return rates, where reported, ranging from 32% to 46%. Based on a report of psychosocial needs of frontline workers (Waegemakers Lane, 2016a, 2016b), Statistics Canada produced a profile of this work force based on the 2016 Canadian census (Statistics Canada, 2019) which closely matched our results and provided strong external validity of data collected. This, in turn, supports the strength of our methodology.
As stress and PTSD lead to avoidance of related triggers, there is undoubtedly a selection bias in respondents who are coping with high stress levels are more likely to avoid additional stress or extra work required to complete a survey. The probability that those most impacted are least likely to participate in these surveys is quite high and results would skew results and underestimate true prevalence and severity. Our methodology aimed to avoid this limitation.
Over 85% of eligible organizations agreed to participate, and resultant data collection of surveys during work hours resulted in response rates varying from 85% to 100% in these organizations. Resultantly, we surveyed most eligible staff. In 2020, we applied for and received a grant from the Canadian Institutes for Health Research (CIHR) to assess COVID-19 specific effects on HSFW staff. The current study includes four additional cities across Canada and a qualitative component consisting of interviews with program administrators to assess organization-level responses. The plan was to replicate the prior research protocols with previously reported high participation rates for a robust result.
Survey recruitment and data collection: most quantitative studies which examine secondary traumatic stress and burnout in human services rely on convenience samples recruited from professional organizations or at training events (Molnar et al., 2020). This self-selection and the ensuing low response rates probably exclude staff most impacted by work-related stress, such as those too busy, tired or burned out to participate in data collection. In turn, this skewed participation could markedly understate the extent of traumatic stress in staff (Halbesleben and Whitman, 2013).
Previous work found that staff participation depended upon organizational leaders providing researchers with time and access to staff during regular working hours. These implementation details were deemed important and are detailed as follows: presenting the study rationale and procedures to staff at staff meetings; designated time for participants go to a private location to (if they chose) complete an anonymous survey; and return the survey in an unmarked envelop directly to researchers. This procedure ensures that the "testing environment", within the workday, is similar across all sites while ensuring that workers who did not want to participate could not be identified. At the conclusion, a wrapup and debriefing session for interested staff to discuss the study and the survey questions was offered. With organizational "buy-in" to the study, it was possible to facilitate a quick and easy data collection resulting in high participation rates, with, depending on site, between 85% and 100% of staff completing the survey.
Previous studies found that rates of traumatic symptoms are indicative of a PTSD diagnosis ranged from 33% to 41% (Schiff and Lane, 2019). Additionally, findings indicated that traumatic stress (i.e. still caring but struggling), and not burnout (i.e. struggling and no longer caring), was the predominant determinant of staff psychosocial distress. This was an important finding, as many interventions to mitigate burnout are not the same as those that can address needs of staff with trauma symptoms. By comparing with previous results, the present study allows us to examine increased rates of traumatic stress due to the pandemic. To ensure that pre-and post-pandemic data were comparable, we aimed to maintain fidelity to the protocols and response rates obtained in the original design.
Protocol modifications: protocol modifications were driven by the pandemic lockdowns and distancing restrictions which limited the mobility of our research team and access to staff within homeless service organizations. While an obvious solution might have been offering the HSFW survey through a secure online platform, we were reluctant and had previously avoided online surveys because of their notoriously low response rates (Shih and Fan, 2008) and consequent limited validity. As a compromise between safety and practicality, we adopted a two-pronged approach including both paper-based and on-line surveys, depending on the specific type of work assignment of staff in each program. Serendipitously, this allowed a comparison of differential response rates across two methodological approaches.
Specific data collection strategies for each organization were determined through discussions with executive directors or CEOs, which allowed them to decide on the most appropriate course of action. Most participating organizations have a combination of staff j HOUSING, CARE AND SUPPORT j deployed to 24/7 shelters, street outreach, and support for those in transitional and "Housing First" programs. Shelter staff were required to continue to work on-site with clients. Those in outreach and support programs had latitude to work from home and plan inperson physically distanced meetings with clients. When possible, staff met with clients virtually and all staff meetings occurred over video conferencing. Staff with whom we could connect over a staff video conference meeting were scheduled for on-line surveys while staff who were primarily in shelters received paper-based surveys. Conflicting requirements for social distancing and working remotely impacted both HSFWs and research assistants (RAs) who were charged with coordinating the different streams of data collection while maintaining social distancing.
Paper-based survey administration: administration of the paper-based surveys was modified in several ways. Previously, research staff distributed the paper surveys. Unable to do so due to COVID-19 restrictions and to reduce perception of coercion on participants by supervisory staff, managers were requested to delegate distribution and collection of the paper-based surveys (in unmarked, sealed envelopes) to staff and to hand-off the surveys to a courier service. To ensure that surveys were distributed according to protocol, a project RA met virtually with HSFW to explain the study, reinforce the importance of procedures, and answer questions. For staff who could not meet with an RA, a senior project RA with COVID-19 quarantine shelter experience developed a short video to help the delegated HSFW complete the study tasks. The video addressed topics including the study rationale, objectives, and key ethical issues (e.g. confidentiality, voluntary participations, etc.). The video was distributed to all potential staff and managerial participants. To answer any questions HSFW may have had before initiating the online survey, the pre-recorded video was accompanied by research staff contact information.
As the pandemic unfolded and worsened, travel prohibitions precluded traveling to deliver or collect completed paper surveys. In some instances, major courier services refused to deliver or collect packages from high-risk places such as soup kitchens and homeless shelters. In some instances, alternative courier services organized by people with lived experiences of homelessness were able to transport the surveys. In others, shelter staff delivered packages of surveys to a central office acceptable to courier services for pick-up.
Internet-based survey administration: administrators at partner organizations reported that not all HSFW had access to computers at work and the means to afford personal computers or the internet at home. This digital divide precluded the opportunity for many shelter staff to complete on-line based surveys during working hours. In some instances, managers and supervisors created workarounds, such as providing staff the time to complete surveys on their mobile phones during work hours, or at the end of their shift, thus maintaining fidelity to survey protocols by completing the survey while at work.
For staff who worked remotely, researchers joined on-line staff meetings, explained the study, answered questions and provided a link to the on-line survey. By pre-arrangement, staff were then allowed to leave the video conference to complete the survey, and then return to the conference for a debrief and wrap-up. During the administration time, employers had no way of knowing if staff were completing the survey or declining to do so, thus ensuring the confidentiality of the participants.
Interviews: a second component of the study was to interview key administrators in each organization. Interviews are a standard feature of qualitative research and can be invaluable in understanding parallel quantitative data. Critical to the collection of in-depth, reliable data, is the context within which interviews are conducted, and researchers provide safe, comfortable, private and confidential location that follow interviewee preferences (Dempsey et al., 2016). These contextual parameters allow for the establishment of rapport and are valuable when the discussion veers to sensitive topics. When interviewing people in positions of authority, it is also paramount that the interviewer is able to probe beyond the j HOUSING, CARE AND SUPPORT j public persona to explore the organizational dynamics that drive its operations. In-person interviews can achieve this through a delicate balance of interaction and empathy. However, when all interviews need to be conducted by video conference, these key dynamics are impeded by several factors, including the challenges of establishing a relationship that is mediated by video technology, limited exposure to the non-verbal communication, including body posture and positioning, lack of eye contact used to establish personal connections and difficulty in determining affective content (Weissman, 2013).
The literature on internet-based qualitative interviewing pre-dates the implementation of video conference technology (Kazmer and Xie, 2008) and does not address the extent to which the visual connect overcomes some of these challenges. Likewise, the literature on the effectiveness of telepsychology and video interviewing is emerging along with its use during the pandemic. Research on psychological services provided through video/distance technology suggests that it can be effective, allowing for reasonable visual and verbal communication of empathy, warmth, and understanding through matched speech, posture, and tone (Dempsey et al., 2016).
In the present study, we considered both the advantages and limitations of conducting all interviews over video conference technology. Video supported online research has been used in fieldwork among vulnerable and sensitive populations for many years (Pink et al., 2015;Weissman, 2017). Due to COVID-19, such virtual fieldwork is becoming more common. The immediate advantage is accessibility. In many instances, video conference technology also translates to a more casual ambience as people worked from home offices and were less constrained by office formalities. The realities that both interviewers and interviewees were facing common pandemic-related operational challenges created a common ground not easily found in situations of hierarchical imbalances of power when interviews occur in a formal office space. A final advantage to these video-based interviews was that some platforms provide a transcript of the meeting at its conclusion. This significantly reduced the time and cost burden of transcription, allowed ready access to the interview content and allowed interviewees opportunity to examine their conversation before formal inclusion in the analyses. In turn, this significantly shortened the time and effort to move to data analysis.
At the same time, conducting video-based interviews did create new challenges. Establishing rapport through a video call may only be partially successful, especially if this is a singular meeting rather than one of a series of conversations. There is a certain type of learning that takes place in dialogues and we call this dialogics. Dialogism is the process by which meaning is derived through conversation in various contexts, where power and status or other factors might influence the meaning of conversations. Recognizing that senior administrators carry certain authority and are often experienced in presenting to the public eye, senior members of the research team who themselves had management and leadership experience conducted these interviews. While this did not completely overcome the limitations of a video call, it allowed interviewers to recognize politically correct answers and those that did not fit with what was known about the organizational dynamics. The senior researchers had extensive interviewing experience in other contexts and were conversant in detecting subtle affective components which may be missed by less experienced persons. Thus, in the review of the transcripts, they were able to identify instances where the transcript did not convey the entire content or context of the issue at hand.
Research staff training: due to COVID-19-related restrictions, training of RAs also occurred online. We used video conferencing to bring cohorts of RA together to train them on all of the study protocols. A senior RA with working experience in shelters had participated in the previous study and provided illustrative examples to the trainee group. This RA also had a firm grasp of the data collection process at staff meetings and was easily able to adapt the revised protocols. Serendipitously, this RA was a trained social worker and also employed as a support worker in a COVID-19 quarantine hotel designated for individuals experiencing homelessness who had tested positive for the virus. This hands-on experience allowed the team to better appreciate the demands placed on frontline workers participating in the study. For example, our experienced RA described to the team how she observed that very few HSFWs were adequately trained to respond in a volatile work environment exacerbated by reactions of clients who were involuntarily detained because of their infectious status.
As this was a nation-wide study, recruitment and coordination of data collection strategies were greatly enhanced by the opportunity to produce and distribute a set of webinars that explained the background, importance of the study and methodologies. These were used across various regions and time zones with the options of offering live broadcasts to attract those who were interested in follow-up discussions. These webinars also paved the way for rapid dissemination of results, which can be done in waves rather than awaiting a final overall report, and was highly encouraged by the funders.
Data entry: a central database allowed for continuous monitoring of the survey responses. Paper surveys were scanned, and electronic versions were sent to RAs for data entry in an identical but separate database from the direct entry version used by staff working remotely. Thus, we could engage in systematic data management of errors/omissions which we expected to be somewhat different between the online and paper versions of the survey. This enabled the team to document the efficacy of online recruitment and participation, both with comparison to a paper-based cohort and also with comparison to results from the same study prior to the pandemic shutdownan analysis that is new to the research literature.
Analysis of preliminary results includes 548 staff in over 40 programs in seven cities. Inperson presentation (n = 210) and on-line (N-338) survey distribution resulted in response rates of over 80% of eligible staff while the online survey participation ranged from 50% to over 80%. Feedback provided indicated that in-person recruitment was favored by participants, some of whom had been included in a previous version of this study and commented on the value of researcher presence. A comparison of participant profiles in one city for which we had data from a similar study conducted in 2019 indicated that the demographic profiles of participants are the same.

Research ethics boards in COVID-19 times
During the pandemic, Research Ethics Boards (REBs) have also quickly refocused their attention toward COVID-19 and research participant safety, adding a new layer of consideration for universities and research staff. Indeed, the present study was based on existing REB-approved protocols, and in non-pandemic times, the new study would have been subject to a request for modification of an existing protocol, with changes including additional study sites and one additional widely used assessment tool. In Canada, research ethics is guided by the Tri-Council Panel on Research Ethics, which issued additional guidelines for research in the COVID-19 environment (https://ethics.gc.ca/eng/nr-cp_2020-09-02.html). The study covered three regions in Canada, and the team had to satisfy the REB of the principal investigator and the REB in each region. The differences in the interpretation of Tri-Council guidelines were apparent across the REBs. Despite substantial research evidence from past iterations of the study and other research that the survey and its imbedded instruments did not pose more than minimal risk, some boards refused to accept this view. Additionally, some REBs adopted a more stringent application of Tri -Council guidelines for determining whether a study is of more than minimal risk: The probability of occurrence of the harm: This refers to the likelihood of participants actually suffering the relevant harms. An assessment of such probability may be based on the researcher's past experience conducting such studies, on the review of existing publications that provide rates of the relevant harms in similar issues, or on other empirical evidence. And while researchers should attempt to estimate the occurrence of the relevant harms, this may be more difficult, or not possible, for new or emerging areas of research where no prior experience, comparable research or publications exist. (https://ethics.gc.ca/eng/tcps2-eptc2_2018_chapter2-chapitre2.html).
Ultimately, our study was deemed to include more than "minimal risk" to participants by a subset of REBs. The irony of this decision is highlighted in the fact that staff works in highrisk settings where trauma exposure is the norm for HSFW and they encounter greater risks in their jobs than the survey presented. This highlights the limitation of REB reviewers who have little first-hand knowledge of specific research environments.
Several aspects of these guidelines received additional attention: privacy and confidentiality issues involved in internet-based research, the need for RAs to connect with staff remotely rather than in face-to-face meetings and potential increase in vulnerabilities for some participants. Under this increased scrutiny, some REBs became much more vigilant of protecting research subjects, even when they do not belong to an identified vulnerable population. This included considerable discussion over the inclusion of a wellknown and widely used instrument on adverse childhood experiences and supplemented existing (approved) questions about major adverse life events. The team perceived this as an intrusion into academic prerogatives over research methodologies.
We raise this issue to stimulate discussion about potential over-interpretation of the risk and harms section of the Tri-Council guidelines. One the one hand, we recognize that the pandemic creates real and severe risks for researchers and research participants. At the same time, research must continue during the pandemicwith reasonable protections in placeto ensure that organizations can create evidence-based, effective policies that mitigate pandemic risk now and, in the future. The net results of our discussions with multiple REBs was a prolonged delay in data collection and therefore access to results by agencies that wanted and needed the data to understand the ongoing support needs of staff.

Limitations
Although we created some economies of time and effort by using video conferencing technology in our study, centralizing online responses and the use of webinars and videos to explain and promote the study, our current response rate varies markedly between online and paper-based data collection and demonstrates that a lack of in-person contact has made recruitment a greater challenge. While a variety approaches have helped recruitment, this does not appear to replace the more personable activities that result when researchers are able to have in-person contact with key administrators and staff in establishing the research partnerships. Recruitment has been impacted by the lack of availability of agency participation during the most acute phases of COVID-19 outbreak when staff are overwhelmed with dealing with active outbreaks of the virus.
Another limitation of our current design is that we have fewer opportunities for student experiential learning than when our data was collected face-to-face. Students, who form the bulk of the data collection team, have worked remotely, which allows them a measure of freedoms and latitude, that can enhance skill-building, but reduces the mentoring that normally accompanies team discussions in a real-time environment. While we have built in debriefing time during the training and shadowing phase of the data collection, it does not fully compensate for the spontaneous discussion about research nuances that can be enriching for students.
Finally, this report focuses on a study that has not completed all of its data collection. There may be additional challenges that could still unfold. One of these emerging issues is the extent to which data collection has to stop during times of infection outbreak because staff are too overwhelmed with increased care duties that there is no appropriate time for them to complete a survey. A second consideration we are monitoring is the extent to which response rates are decreased because the ability for researchers to do in-person presentations of the study is constrained. These interactive discussions are critical not just for framing the study, but also emphasizing the importance and benefits of this research for the direct participants. Although the nature of the project requires that the research be conducted in the midst of this pandemic, the ever-changing circumstances have introduced real and evolving challenges.

Conclusion
Research in organizations serving individuals experiencing homelessness has often neglected the needs of staff who work on the frontlines. In many industries, the COVID-19 pandemic forced all levels of government and senior agency administrators to prioritize the welfare of staff and their needs leading to shutdowns. For some social services, this was simply not possible. The essential nature of the work completed by frontline workers in homeless organizations has led to awareness of the risks that staff encounter on a daily basis that have been exacerbated in the context of COVID-19. The added stress on an already over-burdened work force has been anecdotally reported. The research study that we described has provided an opportunity to learn more about how to conduct research effectively with this difficulty-to-study population, under typical circumstances and in pandemic-specific times.
As a team, assembling over vast distancing, without opportunities to establish working relationships in advance has been a challenge for some members. While the principal investigators had working relationships with other all other team members, they did not have this same connection with each other. The study notes that despite the utility of using video in some contexts, the nature of sporadic video conferencing can limit the opportunities for informal discussions and blurs the visual cuing and social lubricants that generate and stimulate innovations. Hence, the ability to incorporate exigencies into planning and problem solving can be seriously diminished. These adaptations likely translate to a decreased sense of familiarity and cohesion within the team.
From prior iterations of this study, the research team was aware of how to expeditiously solicit and get organizational support for study participation. Social distancing made recruitment more onerous as leadership in many organizations had changed in the last three years and this necessitated working out new connections in the identified organizations. Simultaneously, during outbreaks in respective communities, senior executives struggled with workloads that leave little room for inclusion of research, and simultaneously approached by multiple researchers eager to examine the impact of COVID-19 in various ways, which in turn makes recruitment a greater struggle.
We experienced efficiencies in data collection using on-line surveys that were electronically tabulated and video conferenced interviews that were instantly transcribed. The efficiencies were offset by the need to develop two parallel electronic based surveys, one for staff completion and the other for RAs to data enter paper-based surveys. The perceived efficiency of using an existing REB certification was off-set by the numerous and at times inconsequential requests from review boards that also did not have any experience in how to modify protocols in the face of pandemic distancing requirements. It is premature to conclude if these efficiencies outweighed the burdens of additional accommodations.
A frequently used expression is that the COVID-19 pandemic has provided opportunities to implement new ways of doing things in broad areas. We have explored how these allowed for opportunities and challenges in the context of doing research with staff. Because staff stressors and challenges depend on a full range of responses, the extent to which changes in data collection compromise the soundness of the data will depend on the extent to which this reduced the total participants. The lack of in-person contact in recruitment, RA training and team cohesion may be the most important limitations from adopting new protocols. A post-research analysis of the successes and the results will ultimately determine if research using on-line and social distancing approaches is sufficiently accurate to merit adoption as emerging protocols.


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 .