Search

We evaluated whether hospitalized patients without diagnosed Clostridioides difficile infection (CDI) increased the risk for CDI among their family members after discharge. We used 2001-2017 US insurance claims data to compare monthly CDI incidence between persons in households with and without a family member hospitalized in the previous 60 days. CDI incidence among insurance enrollees exposed to a recently hospitalized family member was 73% greater than enrollees not exposed, and incidence increased with length of hospitalization among family members. We identified a dose-response relationship between total days of within-household hospitalization and CDI incidence rate ratio. Compared with persons whose family members were hospitalized1 day, the incidence rate ratio increased from 1.30 (95% CI 1.19-1.41) for 1-3 days of hospitalization to 2.45 (95% CI 1.66-3.60) for30 days of hospitalization. Asymptomatic C. difficile carriers discharged from hospitals could be a major source of community-associated CDI cases.

Objective:To determine whether Clostridioides difficile infection (CDI) exhibits spatiotemporal interaction and clustering.Design:Retrospective observational study.Setting:The University of Iowa Hospitals and Clinics.Patients:This study included 1,963 CDI cases, January 2005 through December 2011.Methods:We extracted location and time information for each case and ran the Knox, Mantel, and mean and maximum component size tests for time thresholds (T = 7, 14, and 21 days) and distance thresholds (D = 2, 3, 4, and 5 units; 1 unit = 5–6 m). All tests were implemented using Monte Carlo simulations, and random CDI cases were constructed by randomly permuting times of CDI cases 20,000 times. As a counterfactual, we repeated all tests on 790 aspiration pneumonia cases because aspiration pneumonia is a complication without environmental factors.Results:Results from the Knox test and mean component size test rejected the null hypothesis of no spatiotemporal interaction (P < .0001), for all values of T and D. Results from the Mantel test also rejected the hypothesis of no spatiotemporal interaction (P < .0003). The same tests showed no such effects for aspiration pneumonia. Our results from the maximum component size tests showed similar trends, but they were not consistently significant, possibly because CDI outbreaks attributable to the environment were relatively small.Conclusion:Our results clearly show spatiotemporal interaction and clustering among CDI cases and none whatsoever for aspiration pneumonia cases. These results strongly suggest that environmental factors play a role in the onset of some CDI cases. However, our results are not inconsistent with the possibility that many genetically unrelated CDI cases occurred during the study period.

Objective:To estimate the burden of Clostridium difficile infections (CDIs) due to interfacility patient sharing at regional and hospital levels.Design:Retrospective observational study.Methods:We used data from the Healthcare Cost and Utilization Project California State Inpatient Database (2005–2011) to identify 26,878,498 admissions and 532,925 patient transfers. We constructed a weighted, directed network among the hospitals by defining an edge between 2 hospitals to be the monthly average number of patients discharged from one hospital and admitted to another on the same day. We then used a network autocorrelation model to study the effect of the patient sharing network on the monthly average number of CDI cases per hospital, and we estimated the proportion of CDI cases attributable to the network.Results:We found that 13% (95% confidence interval [CI], 7.6%–18%) of CDI cases were due to diffusion through the patient-sharing network. The network autocorrelation parameter was estimated at 5.0 (95% CI, 3.0–6.9). An increase in the number of patients transferred into and/or an increased CDI rate at the hospitals from which those patients originated led to an increase in the number of CDIs in the receiving hospital.Conclusions:A minority but substantial burden of CDI infections are attributable to hospital transfers. A hospital’s infection control may thus be nontrivially influenced by its neighboring hospitals. This work adds to the growing body of evidence that intervention strategies designed to minimize HAIs should be done at the regional rather than local level.

COVID-19 has caused an enormous burden on healthcare facilities around the world. Cohorting patients and healthcare professionals (HCPs) into "bubbles" has been proposed as an infection-control mechanism. In this paper, we present a novel and flexible model for clustering patient care in healthcare facilities into bubbles in order to minimize infection spread. Our model aims to control a variety of costs to patients/residents and HCPs so as to avoid hidden, downstream adverse effects of clustering patient care. This model leads to a discrete optimization problem that we call the BubbleClustering problem. This problem takes as input a temporal visit graph, representing HCP mobility, including visits by HCPs to patient/resident rooms. The output of the problem is a rewired visit graph, obtained by partitioning HCPs and patient rooms into bubbles and rewiring HCP visits to patient rooms so that patient-care is largely confined to the constructed bubbles. Even though the BubbleClustering problem is intractable in general, we present an integer linear programming (ILP) formulation of the problem that can be solved optimally for problem instances that arise from typical hospital units and long-term-care facilities. We call our overall solution approach Cost-aware Rewiring of Networks (CoRN). We evaluate CoRN using fine-grained-movement data from a hospital-medical-intensive-care unit as well as two long-term-care facilities. These data were obtained using sensor systems we built and deployed. The main takeaway from our experimental results is that it is possible to use CoRN to substantially reduce infection spread by cohorting patients and HCPs without sacrificing patient-care, and with minimal excess costs to HCPs in terms of time and distances traveled during a shift., To appear in IEEE ICHI 2021

Background Clostridioides difficile infection (CDI) is a common healthcare-associated infection and is often used as an indicator of hospital safety or quality. However, healthcare exposures occurring prior to hospitalization may increase risk for CDI. We conducted a case-control study comparing hospitalized patients with and without CDI to determine if healthcare exposures prior to hospitalization (ie, clinic visits, antibiotics, family members with CDI) were associated with increased risk for hospital-onset CDI, and how risk varied with time between exposure and hospitalization. Methods Records were collected from a large insurance-claims database from 2001 to 2017 for hospitalized adult patients. Prior healthcare exposures were identified using inpatient, outpatient, emergency department, and prescription drug claims; results were compared between various CDI case definitions. Results Hospitalized patients with CDI had significantly more frequent healthcare exposures prior to admission. Healthcare visits, antibiotic use, and family exposures were associated with greater likelihood of CDI during hospitalization. The degree of association diminished with time between exposure and hospitalization. Results were consistent across CDI case definitions. Conclusions Many different prior healthcare exposures appear to increase risk for CDI presenting during hospitalization. Moreover, patients with CDI typically have multiple exposures prior to admission, confounding the ability to attribute cases to a particular stay.

This paper describes a data-driven simulation study that explores the relative impact of several low-cost and practical non-pharmaceutical interventions on the spread of COVID-19 in an outpatient hospital dialysis unit. The interventions considered include: (i) voluntary self-isolation of healthcare personnel (HCPs) with symptoms; (ii) a program of active syndromic surveillance and compulsory isolation of HCPs; (iii) the use of masks or respirators by patients and HCPs; (iv) improved social distancing among HCPs; (v) increased physical separation of dialysis stations; and (vi) patient isolation combined with preemptive isolation of exposed HCPs. Our simulations show that under conditions that existed prior to the COVID-19 outbreak, extremely high rates of COVID-19 infection can result in a dialysis unit. In simulations under worst-case modeling assumptions, a combination of relatively inexpensive interventions such as requiring surgical masks for everyone, encouraging social distancing between healthcare professionals (HCPs), slightly increasing the physical distance between dialysis stations, and—once the first symptomatic patient is detected—isolating that patient, replacing the HCP having had the most exposure to that patient, and relatively short-term use of N95 respirators by other HCPs can lead to a substantial reduction in both the attack rate and the likelihood of any spread beyond patient zero. For example, in a scenario with R0 = 3.0, 60% presymptomatic viral shedding, and a dialysis patient being the infection source, the attack rate falls from 87.8% at baseline to 34.6% with this intervention bundle. Furthermore, the likelihood of having no additional infections increases from 6.2% at baseline to 32.4% with this intervention bundle., Author summary As we write this, the COVID-19 pandemic has essentially taken over the world, with more than 20 million cases spread over 216 countries. A big concern for policy makers all across the world has been the impact of COVID-19 on healthcare systems and whether these systems can cope with the enormous strain placed on them by COVID-19. In this paper, we consider the spread of COVID-19 in a specific healthcare setting: the outpatient dialysis unit. Hemodialysis patients are extremely vulnerable to infections in large part due to multiple immune-system deficiencies associated with renal failure and hemodialysis. Hemodialysis facilities also increase the risk of COVID-19 transmission because each patient is in frequent, close contact with other patients and healthcare personnel. Thus, a dialysis unit can be seen as a microcosm for the worst-case impacts of COVID-19 in a healthcare setting. In this manuscript, we show via high-fidelity modeling and simulations that under pessimistic modeling assumptions, there is a combination of relatively simple, inexpensive, and practical non-pharmaceutical interventions that can substantially lower the impact of COVID-19 in the dialysis unit. Our simulations are based on fine-grained healthcare personnel movement data that we make available for other modelers to use.

Key Points Question Is exposure to a family member with Clostridioides difficile infection associated with a greater risk for acquiring C difficile infection in exposed individuals? Findings In this case-control study of 224 818 cases of C difficile infection representing 194 424 insurance plan enrollees, having a family member with C difficile infection was significantly associated with increased incidence of C difficile infection, even after controlling for other factors. Meaning Findings from this study suggest that home environment may be a risk factor in the transmission and acquisition of C difficile infection., Importance Clostridioides difficile infection (CDI) is a common hospital-acquired infection. Whether family members are more likely to experience a CDI following CDI in another separate family member remains to be studied. Objective To determine the incidence of potential family transmission of CDI. Design, Setting, and Participants In this case-control study comparing the incidence of CDI among individuals with prior exposure to a family member with CDI to those without prior family exposure, individuals were binned into monthly enrollment strata based on exposure status (eg, family exposure) and confounding factors (eg, age, prior antibiotic use). Data were derived from population-based, longitudinal commercial insurance claims from the Truven Marketscan Commercial Claims and Encounters and Medicare Supplemental databases from 2001 to 2017. Households with at least 2 family members continuously enrolled for at least 1 month were eligible. CDI incidence was computed within each stratum. A regression model was used to compare incidence of CDI while controlling for possible confounding characteristics. Exposures Index CDI cases were identified using inpatient and outpatient diagnosis codes. Exposure risks 60 days prior to infection included CDI diagnosed in another family member, prior hospitalization, and antibiotic use. Main Outcomes and Measures The primary outcome was the incidence of CDI in a given monthly enrollment stratum. Separate analyses were considered for CDI diagnosed in outpatient or hospital settings. Results A total of 224 818 cases of CDI, representing 194 424 enrollees (55.9% female; mean [SD] age, 52.8 [22.2] years) occurred in families with at least 2 enrollees. Of these, 1074 CDI events (4.8%) occurred following CDI diagnosis in a separate family member. Prior family exposure was significantly associated with increased incidence of CDI, with an incidence rate ratio (IRR) of 12.47 (95% CI, 8.86-16.97); this prior family exposure represented the factor with the second highest IRR behind hospital exposure (IRR, 16.18 [95% CI, 15.31-17.10]). For community-onset CDI cases without prior hospitalization, the IRR for family exposure was 21.74 (95% CI, 15.12-30.01). Age (IRR, 9.90 [95% CI, 8.92-10.98] for ages ≥65 years compared with ages 0-17 years), antibiotic use (IRR, 3.73 [95% CI, 3.41-4.08] for low-risk and 14.26 [95% CI, 13.27-15.31] for high-risk antibiotics compared with no antibiotics), and female sex (IRR, 1.44 [95% CI, 1.36-1.53]) were also positively associated with incidence. Conclusions and Relevance This study found that individuals with family exposure may be at significantly greater risk for acquiring CDI, which highlights the importance of the shared environment in the transmission and acquisition of C difficile., This case-control study uses data from 2001 to 2017 to assess the transmission of Clostridioides difficile infection in family members in a household with another family member with primary C difficile infection.

To determine whether Clostridioides difficile infection (CDI) exhibits spatiotemporal interaction and clustering.Retrospective observational study.The University of Iowa Hospitals and Clinics.This study included 1,963 CDI cases, January 2005 through December 2011.We extracted location and time information for each case and ran the Knox, Mantel, and mean and maximum component size tests for time thresholds (T = 7, 14, and 21 days) and distance thresholds (D = 2, 3, 4, and 5 units; 1 unit = 5-6 m). All tests were implemented using Monte Carlo simulations, and random CDI cases were constructed by randomly permuting times of CDI cases 20,000 times. As a counterfactual, we repeated all tests on 790 aspiration pneumonia cases because aspiration pneumonia is a complication without environmental factors.Results from the Knox test and mean component size test rejected the null hypothesis of no spatiotemporal interaction (P.0001), for all values of T and D. Results from the Mantel test also rejected the hypothesis of no spatiotemporal interaction (P.0003). The same tests showed no such effects for aspiration pneumonia. Our results from the maximum component size tests showed similar trends, but they were not consistently significant, possibly because CDI outbreaks attributable to the environment were relatively small.Our results clearly show spatiotemporal interaction and clustering among CDI cases and none whatsoever for aspiration pneumonia cases. These results strongly suggest that environmental factors play a role in the onset of some CDI cases. However, our results are not inconsistent with the possibility that many genetically unrelated CDI cases occurred during the study period.

We investigate graph problems in the following setting: we are given a graph $G$ and we are required to solve a problem on $G^2$. While we focus mostly on exploring this theme in the distributed CONGEST model, we show new results and surprising connections to the centralized model of computation. In the CONGEST model, it is natural to expect that problems on $G^2$ would be quite difficult to solve efficiently on $G$, due to congestion. However, we show that the picture is both more complicated and more interesting. Specifically, we encounter two phenomena acting in opposing directions: (i) slowdown due to congestion and (ii) speedup due to structural properties of $G^2$. We demonstrate these two phenomena via two fundamental graph problems, namely, Minimum Vertex Cover (MVC) and Minimum Dominating Set (MDS). Among our many contributions, the highlights are the following. - In the CONGEST model, we show an $O(n/\epsilon)$-round $(1+\epsilon)$-approximation algorithm for MVC on $G^2$, while no $o(n^2)$-round algorithm is known for any better-than-2 approximation for MVC on $G$. - We show a centralized polynomial time $5/3$-approximation algorithm for MVC on $G^2$, whereas a better-than-2 approximation is UGC-hard for $G$. - In contrast, for MDS, in the CONGEST model, we show an $\tilde{\Omega}(n^2)$ lower bound for a constant approximation factor for MDS on $G^2$, whereas an $\Omega(n^2)$ lower bound for MDS on $G$ is known only for exact computation. In addition to these highlighted results, we prove a number of other results in the distributed CONGEST model including an $\tilde{\Omega}(n^2)$ lower bound for computing an exact solution to MVC on $G^2$, a conditional hardness result for obtaining a $(1+\epsilon)$-approximation to MVC on $G^2$, and an $O(\log \Delta)$-approximation to the MDS problem on $G^2$ in $\mbox{poly}\log n$ rounds., Comment: Appears in PODC 2020. 40 pages, 7 figures

We prove three new lower bounds for graph connectivity in the 1-bit broadcast congested clique model, BCC(1). First, in the KT-0 version of BCC(1), in which nodes are aware of neighbors only through port numbers, we show an Ω(log n) round lower bound for Connectivity even for constant-error randomized Monte Carlo algorithms. The deterministic version of this result can be obtained via the well-known "edge-crossing" argument, but, the randomized version of this result requires establishing new combinatorial results regarding the indistinguishability graph induced by inputs. In our second result, we show that the Ω(log n) lower bound result extends to the KT-1 version of the BCC(1) model, in which nodes are aware of IDs of all neighbors, though our proof works only for deterministic algorithms. This result substantially improves upon the existing Ω(log^* n) deterministic lower bound (Jurdziński et el., SIROCCO 2018) for this problem. Since nodes know IDs of their neighbors in the KT-1 model, it is no longer possible to play "edge-crossing" tricks; instead we present a reduction from the 2-party communication complexity problem Partition in which Alice and Bob are given two set partitions on [n] and are required to determine if the join of these two set partitions equals the trivial one-part set partition. While our KT-1 Connectivity lower bound holds only for deterministic algorithms, in our third result we extend this Ω(log n) KT-1 lower bound to constant-error Monte Carlo algorithms for the closely related ConnectedComponents problem. We use information-theoretic techniques to obtain this result. All our results hold for the seemingly easy special case of Connectivity in which an algorithm has to distinguish an instance with one cycle from an instance with multiple cycles. Our results showcase three rather different lower bound techniques and lay the groundwork for further improvements in lower bounds for Connectivity in the BCC(1) model., LIPIcs, Vol. 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020), pages 32:1-32:17

Background: In the field of public health, network models are useful for understanding the spread of both information and infectious diseases. Collecting network data requires determining network boundaries (ie, the entities selected for data collection). These decisions, if not made carefully, have potential outsized downstream effects on study findings. In practice, collaboration and coordination between healthcare organizations are often dictated by historical or geopolitical boundaries (eg, state or county boundaries), which may distort the underlying network under study, and thereby affect the reliability and/or accuracy of the network model. Objective: We compared natural communities in a patient-sharing network with those induced by geopolitical boundaries. Methods: Using data from the Healthcare Cost and Utilization Project (HCUP), we constructed a patient-sharing network among hospitals in California, splitting the data into a training set and a holdout set. We performed edge-betweenness clustering on the training set, and with the holdout set, we compared the resulting partition with the partition by counties using modularity. We also clustered contiguous counties that might function more cohesively together than individually. We performed spatially constrained hierarchical clustering on the network constructed from total patient flow between pairs of counties. The results were again compared via modularity on the holdout set to the county partition. Lastly, we built an individual-based model (IBM) using HCUP and American Hospital Association data to perform epidemic simulations. For each of several counties, we implemented this model to estimate the proportion of patients infected over time. We then reran the individual-based model using the entire state while dividing the results into corresponding counties. Results: In total, 680,485 patients transferred between 374 hospitals in 55 counties from 2003 to 2011. The out-of-sample modularity for the edge-betweenness clustering partition was 464% higher than that of the county partition. Aggregating the counties into half as many contiguous clusters was 319% higher, and aggregating them into 6 clusters was 489% higher (Fig. 1). The epicurves from the individual-based model ranged from small to significant deviations between state versus county boundaries (Fig. 2) . Conclusions: Collecting network data using externally imposed boundaries may lead to inaccurate network models. For example, counties serve as a poor proxy for their underlying communities, resulting in poor overall disease spread simulation results when county boundaries are allowed to drive network construction. These issues should be considered when building coordination partnerships such as the Accountable Communities for Health.Funding: NoneDisclosures: None

Background:Clostridioides difficile infections (CDIs) present and are transmitted in both community and healthcare settings. Patients who become colonized or infected during hospitalization may be discharged into the community. Asymptomatic spread and/or community-based transmission have also been posited as alternative sources for healthcare-onset CDI cases. The objective of our study was to determine whether individuals are at greater risk for developing a CDI if they have a family member that spent time hospitalized in the prior 90 days, even if the hospitalized family member had no prior diagnosis of CDI. Methods: We conducted a retrospective cohort study using the Truven Marketscan database from 2001 through 2017; both commercial claims and Medicare supplemental data were included. We categorized enrollees by age, sex, month, year, exposure to a family member with CDI, hospitalization, or high- or low-risk antibiotic use in the prior 90 days. We then subdivided these groups based on the total amount of time that other family members spent hospitalized in the prior 90 days: ≤4 days, 5–10, 11–20, 21–30, 41–50 or >50 days. Within each subgroup, we computed the incidence of CDI. We then used a stratified regression model (log-linear quasi-Poisson) to estimate the incidence of CDI in each enrollment bin. Finally, we repeated our analysis using all CDI cases, CDI cases with no prior CDI in the family, and cases without prior hospitalization. Results: Over the 17-year study period, >5.1 billion enrollment months were represented in our dataset. We identified 224,818 cases of CDI, 223,744 cases without prior CDI in a family member and 164,650 CDI cases where the case patient had no prior hospitalization. Table 1 depicts the estimated risk (incident rate ratios) associated with the amount of time that other family members spent hospitalized in the prior 90 days. There is a very clear dose–response curve, and the relative risk for CDI increase as the amount of time other family members spent hospitalized increased. Other risk factors included prior hospitalization, low- and high-risk antibiotics, age, female sex and exposure to a family member with CDI. Conclusions: Having a family member who has been hospitalized in the prior 90 days significantly increases the risk for CDI, even if the family member did not have CDI. The total amount of time other family members spent in the hospital is positively associated with the level of risk.Funding: CDC Modeling Infectious Diseases (MInD) in Healthcare NetworkDisclosures: None

Background: Mobility patterns of healthcare workers (HCWs) (ie, the spatiotemporal distribution of patient rooms they visit) have a significant impact on the spread of healthcare acquired infections (HAIs). Objective: In this project, we used fine-grained data from a sensor deployment at the medical intensive care unit (MICU) in the University of Iowa Hospitals and Clinics (UIHC) to study the mobility patterns of HCWs and their impact on HAI spread. Methods: We analyzed 10 days of data from a 20-bed MICU sensor deployment. For parameters t1 and t2, each pair of rooms i and j is assigned a weight W(i, j) representing the number of times an HCW spends at least t1 seconds in room i followed by at least t1 seconds in room j, within t2 seconds of each other. W(i, j) is a measure of HCW traffic going from room i to room j; we study the correlation between W(i, j) and the distance between rooms i and j. Additionally, we perform 2 disease-spread simulations: (1) a base simulation, obtained by replaying observed HCW mobility traces and (2) a perturbed simulation, which is the same as the base simulation, except that we replace each HCW who visits a room by a random available HCW. Thus, the perturbed simulation removes correlations in the observed HCW mobility traces. Results: We computed W(i, j) for all room pairs i, j for parameters t1 = 30 seconds and t2 = 1,800 and 3,600 seconds. For nurses, there was a strong negative correlation of between pairwise room distance and the weights W(i, j) (−0.768 for t2 = 1,800; −0.711 for t2 = 3,600), The more distant 2 rooms were, the less they shared nurse traffic. This was not true for physicians (correlation = −0.027 for t2 = 1,800; −0.014 for t2 = 3,600). Figure 1 shows a weight versus distance scatter plot for nurses for t1 = 30 and t2 = 1,800. This spatial correlation has positive implications for disease spread; the base simulation, which preserves these spatial correlations, has between 12% and 55% fewer mean infected patients (>100 replicates) for different simulation parameters compared to the perturbed simulation. Conclusions: Our results, based on fine-grained data, show a “naturally emerging” cohorting behavior of nurses, where nurses are more likely to visit rooms close to each other within a 30–60 minute time window, than rooms further away. Through simulations, this behavior provides substantial protection against disease spread.Funding: NoneDisclosures: None

Background:Clostridioides difficile is a leading cause of healthcare-associated infections, and greater healthcare exposure is a primary risk factor for Clostridioides difficile infection (CDI). Longer hospital stays and greater CDI pressure, both at the hospital level and the level, have been linked to greater risk. In addition, symptoms associated with healthcare-associated CDI often do not present until a patient has been discharged. Our study objective was to estimate the extent to which exposure to different types of healthcare settings (eg, prior hospitalization, emergency department [ED], outpatient or long-term care) increase risk for hospital-onset CDI. Methods: We conducted a case-control study using the Truven Marketscan Commerical Claims and Medicare Supplemental databases from 2001 to 2017. Case patients were selected as all inpatient visits with a secondary diagnosis of CDI and no previous CDI diagnosis in the prior 90 days. Controls were selected from all inpatient admissions without any CDI diagnosis during the current admission or prior 90 days. A logistic regression model was used to estimate risk associated with prior healthcare exposure. Indicators were created for prior exposure to different healthcare settings: separate indicators were used to indicate transfer, exposure to that setting in the prior 1–30 days, 31–60 days and 61–90 days. Separate indicators were created for prior hospitalization, ED, outpatient clinic, nursing home or long-term care facilities (LTCFs), psychiatric or substance-abuse facility or other outpatient facility. We also included an indicator for prior exposure to a family member with CDI and prior outpatient antibiotics. Results: Estimates for selected variables (odds ratios) are presented in Table 1. Prior hospitalization, ED visits, outpatient clinics, nursing home and LTCFs were all associated with increased risk of secondary diagnosed CDI. Prior hospitalization and nursing home/LTCF conveyed the greatest risk. In addition, a ‘dose-–response’ relationship occurred for each of these exposure settings, with exposure nearest the admission date having the largest risk. Prior exposure to psychiatric , substance abuse, or other outpatient facilities were not risk factors for CDI. Having a family member with prior CDI and both low-risk and high-risk outpatient antibiotics were associated with increased risk. These factors also exhibited a ‘dose–response’ pattern. Conclusions: Exposure to various healthcare settings significantly increased risk for secondary CDI. Prior healthcare exposures occurring nearest to the point of admission conveyed the greatest risk. These results suggest that many hospital-associated CDI cases attributed to a current hospital stay may actually be acquired from prior healthcare settings.Funding: CDC Modeling Infectious Diseases (MInD) in Healthcare NetworkDisclosures: None

This paper presents a high-fidelity agent-based simulation of the spread of methicillin-resistant Staphylococcus aureus (MRSA), a serious hospital acquired infection, within the dialysis unit at the University of Iowa Hospitals and Clinics (UIHC). The simulation is based on ten days of fine-grained healthcare worker (HCW) movement and interaction data collected from a sensor mote instrumentation of the dialysis unit by our research group in the fall of 2013. The simulation layers a detailed model of MRSA pathogen transfer, die-off, shedding, and infection on top of agent interactions obtained from data. The specific question this paper focuses on is whether there are simple, inexpensive architectural or process changes one can make in the dialysis unit to reduce the spread of MRSA? We evaluate two architectural changes of the nurses' station: (i) splitting the central nurses' station into two smaller distinct nurses' stations, and (ii) doubling the surface area of the nursing station. The first architectural change is modeled as a graph partitioning problem on a HCW contact network obtained from our HCW movement data. Somewhat counter-intuitively, our results suggest that the first architectural modification and the resulting reduction in HCW-HCW contacts has little to no effect on the spread of MRSA and may in fact lead to an increase in MRSA infection counts in some cases. In contrast, the second modification leads to a substantial reduction - between 12% and 22% for simulations with different parameters - in the number of patients infected by MRSA. These results suggest that the dynamics of an environmentally mediated infection such as MRSA may be quite different from that of infections whose spread is not substantially affected by the environment (e.g., respiratory infections or influenza).

Background: Patient sharing between hospitals has long been known to be a contributor to the regional transmission of hospital-acquired infections. This inter–healthcare-facility connectedness suggests that regional, as opposed to local, control and surveillance strategies should be favored. However, the absence of easily and universally accessible patient transfer data hampers researchers and public health agencies who wish to build accurate network models of interfacility transmissions. Medicare data offer only a biased subsample of the full patient transfer network, but because it is widely available, this data source has historically been used for inference and simulation studies. Objective: The purpose of this study was to determine whether Medicare data could successfully be recalibrated to more closely resemble 100% inpatient capture data. Methods: We used data from the Healthcare Cost and Utilization Project (HCUP) to construct 100% capture and Medicare-only patient sharing networks among hospitals in Iowa, Wisconsin, and Nebraska. We used matrix decomposition techniques on the Medicare-only networks along with hospital characteristics from the American Hospital Association (AHA) data for feature construction in a truncated Poisson regression model, and we used Monte Carlo integration to obtain predicted values. These predicted values served as calibrated Medicare-only networks. We split the patient transfer data into training and testing sets and computed the mean squared prediction error (MSPE) for the testing data. We also built an individual based model (IBM) using HCUP and AHA data to perform epidemic simulations that depended on a matrix of patient transfer rates between hospitals. We then compared epicurves from these IBMs resulting from 100% capture networks, Medicare-only networks, and our calibrated networks. Results: Our calibrated networks reduced the MSPE with respect to Medicare-only networks by 84%, 47%, and 88% for Iowa, Wisconsin, and Nebraska, respectively. Although the epicurves from Medicare-only networks differed considerably from that from 100% capture networks, our calibrated networks retained high fidelity to the curves obtained from 100% capture networks. Conclusions: Medicare-only networks greatly underestimate the number of patients transferred between hospitals. Our approach allows us to use Medicare data to estimate networks when 100% inpatient capture is unavailable.Funding: NoneDisclosures: None

Background. Colonization pressure at the unit level is known to be a risk factor for Clostridioides difficile infections in hospitals. Because C. difficile colonization is not routinely detected in clinical practice, only patients identified as having C. difficile infection (CDI) are included in these pressure calculations. We used data from the University of Iowa Hospitals and Clinics (UIHC) to determine whether highly local CDI pressure, due to patients in nearby rooms, is more strongly correlated with CDI than unit-level CDI pressure. Methods: We designed a base logistic regression model using variables known to be risk factors for CDI: age, antibiotic/gastric acid suppressor use, low albumin, prior hospitalization, comorbidities. To the base model, we add 2 measures, mean colonization pressure (MCP) and sum colonization pressure (SCP) of CDI at the unit level to obtain new models. To the base model, we also added CDI colonization pressure by considering CDI cases at different distance thresholds from the focal patient. Distances between patient rooms were extracted from hospital floor plans. Results: Adding unit-level CDI colonization pressures to the base model improved performance. However, adding CDI colonization pressures due to roommates and due to patients at different distances improved the model much more (Table 1). The top (resp. bottom) row shows in-sample (resp. out-of-sample) C-statistics for the base model, the base model with unit-level MCP, the base model with roommate MCP, and the base model with MCP from patients are different distances added as separate features. C-statistics for the base model and the base model with unit CDI pressure (SCP and MCP) are compared in Fig. 1 with C-statistics from the base model with CDI pressure from patients at distances D = 0, 1, 2, 3, 4, 5, 10, 15, 20 hops (1 hop = 5–6 meters). Conclusions: Our results support the hypothesis that unit CDI colonization pressure is a risk factor for CDI. However, by incorporating spatially granular notions of distances between patients in our analysis, we were able to demonstrate that the true source of CDI pressure at the UIHC is almost exclusively attributable to roommates and patients in adjacent rooms.Funding: NoneDisclosures: None

Background: Hospital-acquired infections are commonly spread through the movement of healthcare professionals (HCPs). Computational simulations provide a powerful tool for understanding how HCP behavior contributes to these infections, but how well they reflect the real world rests on a number of critical parameters. Our goal is to provide accurate, fine-grained estimates of real HCP movement and interaction parameters suitable for simulating the potential spread of pathogens over different types of inpatient facilities. Methods: We obtained a commercial data set with 44 million deidentified elements compiled from >27,000 HCPs from >30 job types. The data were collected over 27 months from >20 facilities of varying size using a proprietary electronic sensor system. Each observation recorded an HCP visiting 1 of 12,000 rooms (38% being patient rooms) and consisted of the entry and exit time stamps, hand hygiene behavior, and for many rooms, their (x, y) geometric coordinates within the facility. From these data, we can reconstruct the behavior (including location and hand-hygiene adherence) of each instrumented HCP across multiple shifts. Results: Distributions describing various aspects of HCP behavior (eg, arrival rates and dwell times) were derived using HCP job function, department or unit assignment, type of shift (day vs night), time of day, facility size, and staffing of facility. In a similar fashion, we constructed HCP cross-table transition probabilities using job type, room type, department type, unit type, and facility type. These distributions were used to generate reasonable HCP movement and behavior patterns in a simulation environment. Distributions of dwell time were, for the most part, heavy tailed, but they varied by type of job and facility: dwell times over all facilities, job types, and room types averaged ∼339 seconds (SD, 495 seconds), with a mean of maximums by job type of ∼37,168 seconds. However, these distributions differ within job type but across facilities (ie, nurses in 1 facility averaged 397 seconds, but 277 seconds in another) and within facility but across job type. For example, physicians averaged 292 seconds, whereas nurses averaged 397 seconds and physical therapists averaged 861 seconds. Conclusions: Our results provide a unique resource for disease modelers who wish to build meaningful simulations of the transmission of hospital-acquired infections. The scale and diversity of the data gave us the unique capability to provide, with confidence, distinct parameter sets for different types and sizes of healthcare facilities across a wide range of situations.Funding: NoneDisclosures: None

Background: Simulations based on models of healthcare worker (HCW) mobility and contact patterns with patients provide a key tool for understanding spread of healthcare-acquired infections (HAIs). However, simulations suffer from lack of accurate model parameters. This research uses Microsoft Kinect cameras placed in a patient room in the medical intensive care unit (MICU) at the University of Iowa Hospitals and Clinics (UIHC) to obtain reliable distributions of HCW visit length and time spent by HCWs near a patient. These data can inform modeling efforts for understanding HAI spread. Methods: Three Kinect cameras (left, right, and door cameras) were placed in a patient room to track the human body (ie, left/right hands and head) at 30 frames per second. The results reported here are based on 7 randomly selected days from a total of 308 observation days. Each tracked body may have multiple raw segments over the 2 camera regions, which we “stitch” up by matching features (eg, direction, velocity, etc), to obtain complete trajectories. Due to camera noise, in a substantial fraction of the frames bodies display unnatural characteristics including frequent and rapid directional and velocity change. We use unsupervised learning techniques to identify such “ghost” frames and we remove from our analysis bodies that have 20% or more “ghost” frames. Results: The heat map of hand positions (Fig. 1) shows that high-frequency locations are clustered around the bed and more to the patient’s right in accordance with the general medical practice of performing patient exams from their right. HCW visit frequency per hour (mean, 6.952; SD, 2.855) has 2 peaks, 1 during morning shift and 1 during the afternoon shift, with a distinct decrease after midnight. Figure 2 shows visit length (in minutes) distribution (mean, 1.570; SD, 2.679) being dominated by “check in visits” of Conclusions: Using fine-grained data, this research extracts distributions of these critical parameters of HCW–patient interactions: (1) HCW visit length, (2) HCW visit frequency as a function of time of day, and (3) time spent by HCW within touching distance of patient as a function of visit length. To the best of our knowledge, we provide the first reliable estimates of these parameters.Funding: NoneDisclosures: None

Today's distributed systems exist on a scale that was unimaginable only a few decades ago. Distributed systems now can consist of thousands or even millions of computers spread across the entire world. These large systems are often organized into overlay networks—networks composed of virtual links, with each virtual link realized by one or more physical links. Self-stabilizing overlay networks promise that, starting from any weakly-connected configuration, the correct network topology is always built. This area of research is young, and prior examples of self-stabilizing overlay networks have either been for simple topologies, or involved complex algorithms that were difficult to verify and extend. We address these limitations in this thesis. First, we present the Transitive Closure Framework, a generic framework to transform any locally-checkable overlay network into a self-stabilizing network. This simple framework has a running time which is at most a logarithmic number of rounds more than optimal, and in fact is optimal for a particular class of overlay networks. We also prove the only known non-trivial lower bound on the convergence time of any self-stabilizing overlay network. To allow fast and efficient repairs for local faults, we extend the Transitive Closure Framework to the Local Repair Framework. We demonstrate this framework by implementing an efficient algorithm for node joins in the Skip+ graph. Next, we present the Avatar network, which is a generic locally checkable overlay network capable of simulating many other overlay networks. We design a self-stabilizing algorithm for a binary search tree embedded onto the Avatar network, and prove this algorithm requires only a polylogarithmic number of rounds to converge and limits degree increases to within a polylogarithmic factor of optimal. This algorithm is the first to achieve such efficiency, and its modular design makes it easy to extend. Finally, we introduce a technique called network scaffolding, which builds other overlay network topologies using the Avatar network.

Distributed Approximation is a new and rapidly developing discipline that lies at the crossroads of various well-established areas of Computer Science - Distributed Computing, Approximation Algorithms, Graph Theory and often, Computational Geometry. This thesis focuses on the design and analysis of distributed algorithms to solve optimization problems that usually arise in large-scale, heavily dynamic, resource constrained networks, e.g. wireless ad-hoc and sensor networks, P2P systems, mobile networks etc. These problems can often be abstracted by variations of well-known combinatorial optimization problems, such as topology control, clustering etc. Many of these problems are known to be hard (NP-complete). But we need fast and light-weight distributed algorithms for these problems, that yield near-optimal solutions. The results presented in this thesis can be broadly divided in two parts. The first part contains a set of results that obtain improved solutions to the classic problem of computing a sparse “backbone” for Wireless Sensor Networks (WSNs). In graph-theoretic terms, the goal is to compute a spanning subgraph of the input graph, that is sparse, lightweight and has low stretch. The term “low stretch” indicates that in spite of dropping many edges, the distance between any two nodes in the graph is not increased by much. We model WSNs as geometric graphs - unit ball graphs, quasi-unit ball graphs etc. in Euclidean spaces, as well as in more general metric spaces of low doubling dimension. We identify and exploit a variety of geometric features of those models to obtain our results. In the second part of the thesis we focus on distributed algorithms for clustering problems. We present several distributed approximation algorithms for clustering problems (e.g., minimum dominating set, facility location problems) that improve on best known results so far. The main contribution here is the design of distributed algorithms where the running time is a “tunable” parameter. The advent of distributed systems of unprecedented scale and complexity motivates the question of whether it is possible to design algorithms that can provide non-trivial approximation guarantees even after very few rounds of computation and message exchanges. We call these algorithms “ k-round algorithms”. We design k-round algorithms for various clustering problems that yield non-trivial approximation factors even if k is a constant. Additionally, if k assumes poly-logarithmic values, our algorithms match or improve on the best-known approximation factors for these problems.

The facility location problem consists of a set of facilities$${\mathcal {F}}$$F, a set of clients$${\mathcal {C}}$$C, an opening cost$$f_i$$fi associated with each facility $$x_i$$xi, and a connection cost$$D(x_i,y_j)$$D(xi,yj) between each facility $$x_i$$xi and client $$y_j$$yj. The goal is to find a subset of facilities to open, and to connect each client to an open facility, so as to minimize the total facility opening costs plus connection costs. We consider distributed versions of facility location in which the underlying network is either a clique, in which each node is both a client and a facility (and $${\mathcal {F}} = {\mathcal {C}}$$F=C), or a complete bipartite network, with $$({\mathcal {F}}, {\mathcal {C}})$$(F,C) forming the bipartition. This paper presents the first expected-sub-logarithmic-round distributed $$O(1)$$O(1)-approximation algorithms in the $${\mathcal {CONGEST}}$$CONGEST model for the metric facility location problem. We present our approach first for a clique network, and then extend it to a bipartite network. Our algorithms have expected running times of $$O((\log \log n)^c)$$O((loglogn)c) rounds, where $$n = |{\mathcal {F}}| + |{\mathcal {C}}|$$n=|F|+|C|, and where $$c = 1$$c=1 for a clique network and $$c = 3$$c=3 for a bipartite network (These results were first published in ICALP 2012 and DISC 2013). In order to obtain these results, our paper makes four main technical contributions. First, we show a new lower bound for metric facility location, extending the lower bound of Ba?doiu et al. (ICALP 2005) that applies only to the special case of uniform facility opening costs. Next, we demonstrate a reduction of the distributed metric facility location problem to the problem of computing an $$O(1)$$O(1)-ruling set of an appropriate spanning subgraph. Third, we provide an expected-sub-logarithmic-round algorithm for computing a $$2$$2-ruling set in a spanning subgraph of a clique. Finally, we present a new technique based on probabilistic hashing to solve a problem of information dissemination on bipartite networks.

The clustering problem, in its many variants, has numerous applications in operations research and computer science (e.g., in applications in bioinformatics, image processing, social network analysis, etc.). As sizes of data sets have grown rapidly, researchers have focused on designing algorithms for clustering problems in models of computation suited for large-scale computation such as MapReduce, Pregel, and streaming models. The $k$-machine model (Klauck et al., SODA 2015) is a simple, message-passing model for large-scale distributed graph processing. This paper considers three of the most prominent examples of clustering problems: the uncapacitated facility location problem, the $p$-median problem, and the $p$-center problem and presents $O(1)$-factor approximation algorithms for these problems running in $\tilde{O}(n/k)$ rounds in the $k$-machine model. These algorithms are optimal up to polylogarithmic factors because this paper also shows $\tilde{\Omega}(n/k)$ lower bounds for obtaining polynomial-factor approximation algorithms for these problems. These are the first results for clustering problems in the $k$-machine model. We assume that the metric provided as input for these clustering problems in only implicitly provided, as an edge-weighted graph and in a nutshell, our main technical contribution is to show that constant-factor approximation algorithms for all three clustering problems can be obtained by learning only a small portion of the input metric.

We study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. Our work is motivated by the following central question: can we break the long-standing Θ(log n) time-complexity barrier and the Θ(m) message-complexity barrier in the Congest model for MIS or closely-related symmetry breaking problems? This paper presents progress towards this question for the distributed ruling set problem in the Congest model. A β-ruling set is an independent set such that every node in the graph is at most β hops from a node in the independent set. We present the following results: Time Complexity: We show that we can break the O(log n) "barrier" for 2- and 3-ruling sets. We compute 3-ruling sets in O((log n)/(log log n)) rounds with high probability (whp). More generally we show that 2-ruling sets can be computed in O(log Δ · (log n)1/2 + e + (log n)/(log log n)) rounds for any e > 0, which is o(log n) for a wide range of Δ values (e.g., Δ = 2(log n)1/2-e). These are the first 2- and 3-ruling set algorithms to improve over the O(log n)-round complexity of Luby's algorithm in the Congest model. Message Complexity: We show an Ω(n2) lower bound on the message complexity of computing an MIS (i.e., 1-ruling set) which holds also for randomized algorithms and present a contrast to this by showing a randomized algorithm for 2-ruling sets that, whp, uses only O(n log2 n) messages and runs in O(Δ log n) rounds. This is the first message-efficient algorithm known for ruling sets, which has message complexity nearly linear in n (which is optimal up to a polylogarithmic factor). Our results are a step toward understanding the time and message complexity of symmetry breaking problems in the Congest model.

Background Understanding how C. diffcile infection (CDI) is acquired in healthcare settings is key to designing interventions to mitigate CDI. The goal of this research is apply statistical methods, typically used to investigate regional outbreaks, to study spatio-temporal clustering of in-hospital CDI incidence. Methods We analyzed 1,804 CDI cases (out of 241,248 in-patient visits) at the University of Iowa Hospitals and Clinics (UIHC) during January 2005–December 2011. Letting T and D be time and space parameters, we constructed an observed CDI cluster graph by connecting pairs of CDI cases whose positive CDI tests occur within T days and D distance units of each other. In Experiment 1, for each CDI case, we replaced its actual time stamp by one picked uniformly at random from the time interval [January 2005, December 2011] and constructed a random CDI cluster graph. We tested the UIHC CDI case counts for seasonality and observed none, but did observe that the CDI counts increased significantly (weekly mean: 4.12–>8.11) starting in December 2009, when the C. diffcile Toxin A&B test was replaced by the C. diffcile Toxin PCR. So, we performed an Experiment 2 in which we sampled time stamps from a mixture of two uniform distributions, representing the periods of the two tests. Results We report sizes of connected components in the table below, for 10,000 trials of Experiments 1 and 2, for T = 14 days and varying D, a one setting in which D is set to the unit in which the CDI case occurs. The plots show the distribution of the mean and maximum component size (blue curves) for Experiment 2, for D = 2. D ObservedMean Comp. Size Experiment 1 Expected Mean Comp. Size (P-value) Experiment 2 Expected Mean Comp. Size (P-value) Observed Max. Comp. Size Experiment 1 Expected Max. Comp. Size (P-value) Experiment 2 Expected Max. Comp Size (P-value) 2 1.12 1.07 (0) 1.06 (0) 6 3.72 (0.01) 4.07 (0.05) 3 1.19 1.11 (0) 1.11 (0) 7 4.61 (0.03) 5.17 (0.1) 5 1.29 1.18 (0) 1.20 (0) 11 6.6 (0.01) 8.10 (0.1) 10 1.93 1.68 (0) 1.52 (0) 29 17.13 (0.02) 28.08 (0.4) Unit 1.63 1.38 (0) 1.01 (0) 23 9.74 (0) 12.87 (0.01) Conclusion Our analysis of the UIHC CDI cases shows significant spatio-temporal clustering in the observed CDI cluster graph. These results suggest that direct or environmental transmission may play a significant role in CDI acquisition at the UIHC. Funded by the CDC MInD-Healthcare. Disclosures All authors: No reported disclosures.

Overlay networks are expected to operate in hostile environments, where node and link failures are commonplace. One way to make overlay networks robust is to design self-stabilizing overlay networks, i.e., overlay networks that can handle node and link failures without any external supervision. In this paper, we first describe a simple framework, which we call the Transitive Closure Framework (TCF), for the selfstabilizing construction of an extensive class of overlay networks. Like previous self-stabilizing overlay networks, TCF permits node degrees to grow to Ω(n), independent of the maximum degree of the target overlay network. However, TCF has several advantages over previous work in this area: (i) it is a "framework" and can be used for the construction of a variety of overlay networks, not just a particular network, (ii) it runs in an optimal number of rounds for a variety of overlay networks, and (iii) it can easily be composed with other non-self-stabilizing protocols that can recover from specific bad initial states in a memory-efficient fashion. We demonstrate the power of our framework by deriving from TCF a simple self-stabilizing protocol for constructing Skip+ graphs (Jacob et al., PODC 2009) which presents optimal convergence time from any configuration, and requires only a O(1) factor of extra memory for handling node Joins.

Until recently, the fastest distributed MIS algorithm, even for simple graphs, e.g., unoriented trees, has been the simple randomized algorithm discovered in the 80s. This algorithm (commonly called Luby's algorithm) computes an MIS in O(log n) rounds (with high probability). This situation changed when Lenzen and Wattenhofer (PODC 2011) presented a randomized O(√log n} ⋅ log\log n)-round MIS algorithm for unoriented trees. This algorithm was improved by Barenboim et al. (FOCS 2012), resulting in an MIS algorithm running in O(√log n ⋅ log\log n) rounds.The analyses of these tree MIS algorithms depends on "near independence" of probabilistic events, a feature of the tree structure of the network. In their paper, Lenzen and Wattenhofer hope that their algorithm and analysis could be extended to graphs with bounded arboricity. We show how to do this in this note. By using a new tail inequality for read-k families of random variables due to Gavinsky et al. Random Struct Algorithms, 2015), we show how to deal with dependencies induced by the recent tree MIS algorithms when they are executed on bounded arboricity graphs. Specifically, we analyze a version of the tree MIS algorithm of Barenboim et al. and show that it runs in O(poly(α) ⋅ √log n ⋅ log log n) rounds in the CONGEST model for arboricity-α graphs.

Given a graph G = ( V, E ) and positive integral vertex weights w : V → N , the max-coloring problem seeks to find a proper vertex coloring of G whose color classes C 1 , C 2 , …, C k , minimize ∑ i =1 k max v ∈ C i w ( v ). This problem, restricted to interval graphs, arises whenever there is a need to design dedicated memory managers that provide better performance than the general-purpose memory management of the operating system. Though this problem seems similar to the dynamic storage allocation problem, there are fundamental differences. We make a connection between max-coloring and online graph coloring and use this to devise a simple 2-approximation algorithm for max-coloring on interval graphs. We also show that a simple first-fit strategy, that is a natural choice for this problem, yields an 8-approximation algorithm. We show this result by proving that the first-fit algorithm for online coloring an interval graph G uses no more than 8 ċ χ( G ) colors, significantly improving the bound of 26 ċ χ( G ) by Kierstead and Qin [1995]. We also show that the max-coloring problem is NP-hard. The problem of online coloring of intervals with bandwidths is a simultaneous generalization of online interval coloring and online bin packing. The input is a set I of intervals, each interval i ∈ I having an associated bandwidth b ( i ) ∈ (0, 1]. We seek an online algorithm that produces a coloring of the intervals such that for any color c and any real r , the sum of the bandwidths of intervals containing r and colored c is at most 1. Motivated by resource allocation problems, Adamy and Erlebach [2003] consider this problem and present an algorithm that uses at most 195 times the number of colors used by an optimal offline algorithm. Using the new analysis of first-fit coloring of interval graphs, we show that the Adamy-Erlebach algorithm is 35-competitive. Finally, we generalize the Adamy-Erlebach algorithm to a class of algorithms and show that a different instance from this class is 30-competitive.

Objective.To use social network analysis to design more effective strategies for vaccinating healthcare workers against influenza.Design.An agent-based simulation.Setting.A simulation based on a 700-bed hospital.Methods.We first observed human contacts (defined as approach within approximately 0.9 m) performed by 15 categories of healthcare workers (eg, floor nurses, intensive care unit nurses, staff physicians, phlebotomists, and respiratory therapists). We then constructed a series of contact graphs to represent the social network of the hospital and used these graphs to run agent-based simulations to model the spread of influenza. A targeted vaccination strategy that preferentially vaccinated more “connected” healthcare workers was compared with other vaccination strategies during simulations with various base vaccination rates, vaccine effectiveness, probability of transmission, duration of infection, and patient length of stay.Results.We recorded 6,654 contacts by 148 workers during 606 hours of observations from January through December 2006. Unit clerks, X-ray technicians, residents and fellows, transporters, and physical and occupational therapists had the most contacts. When repeated contacts with the same individual were excluded, transporters, unit clerks, X-ray technicians, physical and occupational therapists, and social workers had the most contacts. Preferentially vaccinating healthcare workers in more connected job categories yielded a substantially lower attack rate and fewer infections than a random vaccination strategy for all simulation parameters.Conclusions.Social network models can be used to derive more effective vaccination policies, which are crucial during vaccine shortages or in facilities with low vaccination rates. Local vaccination priorities can be determined in any healthcare facility with only a modest investment in collection of observational data on different types of healthcare workers. Our findings and methods (ie, social network analysis and computational simulation) have implications for the design of effective interventions to control a broad range of healthcare-associated infections.

Over the last few years, the problem of computing market equilibrium prices for exchange economies has received much attention in the theoretical computer science community. Such activity led to a flurry of polynomial time algorithms for various restricted, yet significant, settings. The most important restrictions arise either when the traders' utility functions satisfy a property known as gross substitutability or when the initial endowments are proportional (the Fisher model). In this paper, we experimentally compare the performance of some of these recent algorithms against that of the most used software packages. In particular, we evaluate the following approaches: (1) the solver PATH, available under GAMS/MPSGE, a popular tool for computing market equilibrium prices; (2) a discrete version of a simple iterative price update scheme called tâtonnement; (3) a discrete version of the welfare adjustment process; (4) convex feasibility programs that characterize the equilibrium in some special cases. We analyze the performance of these approaches on models of exchange economies where the consumers are equipped with utility functions, which are widely used in real world applications. The outcomes of our experiments consistently show that many market settings allow for an efficient computation of the equilibrium, well beyond the restrictions under which the theory provides polynomial time guarantees. For some of the approaches, we also identify models where they are are prone to failure.

Self-stabilization is an elegant approach for designing a class of fault-tolerant distributed protocols. A self-stabilizing protocol is guaranteed to eventually converge to a legitimate state after a transient fault. However, even a minor transient fault can cause vast disruption in the system before legitimacy is reached. This paper introduces the notion of fault-containment to address this particular weakness of self-stabilizing systems. Informally, a fault-containing self-stabilizing protocol, in addition to providing self- stabilization, contains the effects of faults. This ensures that disruption during recovery from faults, is proportional to the extent of the faults. The paper begins with a formal framework for specifying and evaluating fault-containing self-stabilizing protocols. The main result of the paper is a transformer that converts any non-reactive self-stabilizing protocol into an equivalent fault-containing self-stabilizing protocol that can repair any single fault in the system in O(1) time. For a large class of input protocols, the corresponding output protocols produced by the transformer have O(1) space overhead. The small time and space overhead make the fault-containing self-stabilizing protocol a practical alternative to the original self-stabilizing protocol. The transformer is based on a novel stabilizing timer paradigm that significantly simplifies the task of fault-containment.

Clostridium Difficile Infection (CDI) is a contagious healthcare-associated infection that imposes a significant burden on the healthcare system. In 2011 alone, half a million patients suffered from CDI in the United States, 29,000 dying within 30 days of diagnosis. Determining which hospital patients are at risk for developing CDI is critical to helping healthcare workers take timely measures to prevent or detect and treat this infection. We improve the state of the art of CDI risk prediction by designing an ensemble logistic regression classifier that given partial patient visit histories, outputs the risk of patients acquiring CDI during their current hospital visit. The novelty of our approach lies in the representation of each patient visit as a collection of co-occurring and chronologically ordered pairs of events. This choice is motivated by our hypothesis that CDI risk is influenced not just by individual events (e.g., Being prescribed a first generation cephalosporin antibiotic), but by the temporal ordering of individual events (e.g., Antibiotic prescription followed by transfer to a certain hospital unit). While this choice explodes the number of features, we use a randomized greedy feature selection algorithm followed by BIC minimization to reduce the dimensionality of the feature space, while retaining the most relevant features. We apply our approach to a rich dataset from the University of Iowa Hospitals and Clinics (UIHC), curated from diverse sources, consisting of 200,000 visits (30,000 per year, 2006-2011) involving 125,000 unique patients, 2 million diagnoses, 8 million prescriptions, 400,000 room transfers spanning a hospital with 700 patient rooms and 200 units. Our approach to classification produces better risk predictions (AUC) than existing risk estimators for CDI, even when trained just on data available at patient admission. It also identifies novel risk factors for CDI that are combinations of co-occurring and chronologically ordered events.

We study two fundamental graph problems, Graph Connectivity (GC) and Minimum Spanning Tree (MST), in the well-studied Congested Clique model, and present several new bounds on the time and message complexities of randomized algorithms for these problems. No non-trivial (i.e., super-constant) time lower bounds are known for either of the aforementioned problems; in particular, an important open question is whether or not constant-round algorithms exist for these problems. We make progress toward answering this question by presenting randomized Monte Carlo algorithms for both problems that run in O(log log log n) rounds (where n is the size of the clique). Our results improve by an exponential factor on the long-standing (deterministic) time bound of O(log log n) rounds for these problems due to Lotker et al. (SICOMP 2005). Our algorithms make use of several algorithmic tools including graph sketching, random sampling, and fast sorting.The second contribution of this paper is to present several almost-tight bounds on the message complexity of these problems. Specifically, we show that Ω(n2) messages are needed by any algorithm (including randomized Monte Carlo algorithms, and regardless of the number of rounds) that solves the GC (and hence also the MST) problem if each machine in the Congested Clique has initial knowledge only of itself (the so-called KT0 model). In contrast, if the machines have initial knowledge of their neighbors' IDs (the so-called KT1 model), we present a randomized Monte Carlo algorithm for MST that uses O(n polylog n) messages and runs in O(polylog n) rounds. To complement this, we also present a lower bound in the KT1 model that shows that Ω(n) messages are required by any algorithm that solves GC, regardless of the number of rounds used. Our results are a step toward understanding the power of randomization in the Congested Clique with respect to both time and message complexity.

We show that the problem of finding a minimum dominating set in a circle graph is APX-hard: there is a constant δ > 0 such that there is no (1 + δ)-approximation algorithm for the minimum dominating set problem on circle graphs unless P = NP. Hence a PTAS for this problem seems unlikely. This hardness result complements the (2 + e)-approximation algorithm for the problem [M. Damian, S.V. Pemmaraju, A (2 + e)-approximation scheme for minimum domination on circle graphs, J. Algorithms 42 (2) (2002) 255-276].

An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most 1. A d-degenerate graph is a graph G in which every subgraph has a vertex with degree at most d. A star Sm with m rays is an example of a 1-degenerate graph with maximum degree m that needs at least 1+m/2 colors for an equitable coloring. Our main result is that every n-vertex d-degenerate graph G with maximum degree at most n/15 can be equitably k-colored for each $k \ge 16d$. The proof of this bound is constructive. We extend the algorithm implied in the proof to an O(d)-factor approximation algorithm for equitable coloring of an arbitrary d-degenerate graph. Among the implications of this result is an O(1)-factor approximation algorithm for equitable coloring of planar graphs with fewest colors. A variation of equitable coloring (equitable partitions) is also discussed.

The market equilibrium problem has a long and distinguished history. In 1874, Walras published the famous "Elements of Pure Economics", where he describes a model for the state of an economic system in terms of demand and supply, and expresses the supply equals demand equilibrium conditions [62]. In 1936, Wald gave the first proof of the existence of an equilibrium for the Walrasian system, albeit under severe restrictions [61]. In 1954, Nobel laureates Arrow and Debreu proved the existence of an equilibrium under milder assumptions [3]. This existence result, along with the two fundamental theorems of welfare are the pillars of modern equilibrium theory. The First Fundamental Theorem of Welfare showed the Pareto optimality of allocations at equilibrium prices, thereby formally expressing Adam Smith's "invisible hand" property of markets and providing important social justification for the theory of equilibrium.

The minimum α-small partition problem is the problem of partitioning a given simple polygon into subpolygons, each with diameter at most α, for a given α > 0. This paper considers the version of this problem that disallows Steiner points. This problem is motivated by applications in mesh generation and collision detection. The main result in the paper is a polynomial-time algorithm that solves this problem, and either returns an optimal partition or reports the nonexistence of such a partition. This result contrasts with the recent NP-completeness result for the minimum α-small partition problem for polygons with holes (C. Worman, 15th Canadian Conference on Computational Geometry, 2003). Even though the running time of our algorithm is a polynomial in the input size, it is prohibitive for most real applications and we seek faster algorithms that approximate an optimal solution. We first present a faster 2-approximation algorithm for the problem for simple polygons and then a near linear-time algorithm for convex polygons that produces, for any e > 0, an (α+e)-small partition with no more polygons than in an optimal α-small partition. We also present an exact polynomial-time algorithm for the minimum α-small partition problem with the additional constraint that each piece in the partition be convex.

Objective.To determine whether hand hygiene adherence is influenced by peer effects and, specifically, whether the presence and proximity of other healthcare workers has a positive effect on hand hygiene adherenceDesign.An observational study using a sensor network.Setting.A 20-bed medical intensive care unit at a large university hospital.Participants.Hospital staff assigned to the medical intensive care unit.Methods.We deployed a custom-built, automated, hand hygiene monitoring system that can (1) detect whether a healthcare worker has practiced hand hygiene on entering and exiting a patient’s room and (2) estimate the location of other healthcare workers with respect to each healthcare worker exiting or entering a room.Results.We identified a total of 47,694 in-room and out-of-room hand hygiene opportunities during the 10-day study period. When a worker was alone (no recent healthcare worker contacts), the observed adherence rate was 20.85% (95% confidence interval [CI], 19.78%–21.92%). In contrast, when other healthcare workers were present, observed adherence was 27.90% (95% CI, 27.48%–28.33%). This absolute increase was statistically significant (P < .01). We also found that adherence increased with the number of nearby healthcare workers but at a decreasing rate. These results were consistent at different times of day, for different measures of social context, and after controlling for possible confounding factors.Conclusions.The presence and proximity of other healthcare workers is associated with higher hand hygiene rates. Furthermore, our results also indicate that rates increase as the social environment becomes more crowded, but with diminishing marginal returns.Infect Control Hosp Epidemiol 2014;35(10):1277–1285

A t-ruling set of a graph G = (V, E) is a vertex-subset S ⊆ V that is independent and satisfies the property that every vertex v ∈ V is at a distance of at most t hops from some vertex in S. A maximal independent set (MIS) is a 1-ruling set. Extending results from Kothapalli et al. (FSTTCS 2012) this note presents a randomized algorithm for computing, with high probability, a t-ruling set in O(t ⋅ log1/(t-1)n) rounds for 2 √(log log n).

The main results of this paper are (I) a simulation algorithm which, under quite general constraints, transforms algorithms running on the Congested Clique into algorithms running in the MapReduce model, and (II) a distributed O(Δ)-coloring algorithm running on the Congested Clique which has an expected running time of O(1) rounds, if Δ ≥ Θ(log4 n); and O(logloglogn) rounds otherwise. Applying the simulation theorem to the Congested Clique O(Δ)-coloring algorithm yields an O(1)-round O(Δ)-coloring algorithm in the MapReduce model.

The main results of this paper are (I) a simulation algorithm which, under quite general constraints, transforms algorithms running on the Congested Clique into algorithms running in the MapReduce model, and (II) a distributed $O(\Delta)$-coloring algorithm running on the Congested Clique which has an expected running time of (i) $O(1)$ rounds, if $\Delta \geq \Theta(\log^4 n)$; and (ii) $O(\log \log n)$ rounds otherwise. Applying the simulation theorem to the Congested-Clique $O(\Delta)$-coloring algorithm yields an $O(1)$-round $O(\Delta)$-coloring algorithm in the MapReduce model. Our simulation algorithm illustrates a natural correspondence between per-node bandwidth in the Congested Clique model and memory per machine in the MapReduce model. In the Congested Clique (and more generally, any network in the $\mathcal{CONGEST}$ model), the major impediment to constructing fast algorithms is the $O(\log n)$ restriction on message sizes. Similarly, in the MapReduce model, the combined restrictions on memory per machine and total system memory have a dominant effect on algorithm design. In showing a fairly general simulation algorithm, we highlight the similarities and differences between these models., Comment: 15 pages

This paper presents constant-time and near-constant-time distributed algorithms for a variety of problems in the congested clique model. We show how to compute a 3-ruling set in expected O(logloglogn) rounds and using this, we obtain a constant-approximation to metric facility location, also in expected O(logloglogn) rounds. In addition, assuming an input metric space of constant doubling dimension, we obtain constant-round algorithms to compute constant-factor approximations to the minimum spanning tree and the metric facility location problems. These results significantly improve on the running time of the fastest known algorithms for these problems in the congested clique setting.

Self-stabilizing algorithms recover from all cases of transient failure, but the mechanism of self-stabilization may be costly for mild cases of transient failure. Error-detecting codes can be used to identify, with high probability, transient faults in data. This note investigates how error-detecting codes can enhance self-stabilization to deal efficiently with the common case of single-process transient faults. The main results are characterizations of self-stabilizing algorithms that can use error-detecting codes to recover from single-process transient faults in a single step. (C) 2000 .

Stack layouts and queue layouts of undirected graphs have been used to model problems in fault-tolerant computing and in parallel process scheduling. However, problems in parallel process scheduling are more accurately modeled by stack and queue layouts of directed acyclic graphs (dags). A stack layout of a dag is similar to a stack layout of an undirected graph, with the additional requirement that the nodes of the dag be in some topological order. A queue layout is defined in an analogous manner. The stacknumber ( queuenumber) of a dag is the smallest number of stacks (queues) required for its stack layout (queue layout). In this paper, bounds are established on the stacknumber and queuenumber of two classes of dags: tree dags and unicyclic dags. In particular, any tree dag can be laid out in 1 stack and in at most 2 queues; and any unicyclic dag can be laid out in at most 2 stacks and in at most 2 queues. Forbidden subgraph characterizations of 1-queue tree dags and 1-queue cycle dags are also presented. Part II of this paper presents algorithmic results---in particular, linear time algorithms for recognizing 1-stack dags and 1-queue dags and proof of NP-completeness for the problem of recognizing a 4-queue dag and the problem of recognizing a 9-stack dag.

The stacknumber (queuenumber) of a poset is defined as the stacknumber (queuenumber) of its Hasse diagram viewed as a directed acyclic graph. Upper bounds on the queuenumber of a poset are derived in terms of its jumpnumber, its length, its width, and the queuenumber of its covering graph. A lower bound of $\Omega(\sqrt n)$ is shown for the queuenumber of the class of n-element planar posets. The queuenumber of a planar poset is shown to be within a small constant factor of its width. The stacknumber of n-element posets with planar covering graphs is shown to be $\Theta(n)$. These results exhibit sharp differences between the stacknumber and queuenumber of posets as well as between the stacknumber (queuenumber) of a poset and the stacknumber (queuenumber) of its covering graph.