Filtering by
- All Subjects: Computer Science
- All Subjects: Screening
- Status: Published
The two major issues concerning covering arrays are explicit construction of a covering array, and exact or approximate determination of the covering array number---the minimum size of a covering array. Although these problems have been investigated extensively for the last couple of decades, in this thesis we present significant improvements on both of these questions using tools from the probabilistic method and randomized algorithms.
First, a series of improvements is developed on the previously known upper bounds on covering array numbers. An estimate for the discrete Stein-Lovász-Johnson bound is derived and the Stein- Lovász -Johnson bound is improved upon using an alteration strategy. Then group actions on the set of symbols are explored to establish two asymptotic upper bounds on covering array numbers that are tighter than any of the presently known bounds.
Second, an algorithmic paradigm, called the two-stage framework, is introduced for covering array construction. A number of concrete algorithms from this framework are analyzed, and it is shown that they outperform current methods in the range of parameter values that are of practical relevance. In some cases, a reduction in the number of tests by more than 50% is achieved.
Third, the Lovász local lemma is applied on covering perfect hash families to obtain an upper bound on covering array numbers that is tightest of all known bounds. This bound leads to a Moser-Tardos type algorithm that employs linear algebraic computation over finite fields to construct covering arrays. In some cases, this algorithm outperforms currently used methods by more than an 80% margin.
Finally, partial covering arrays are introduced to investigate a few practically relevant relaxations of the covering requirement. Using probabilistic methods, bounds are obtained on partial covering arrays that are significantly smaller than for covering arrays. Also, randomized algorithms are provided that construct such arrays in expected polynomial time.
As a step in model development, statistically designed screening experiments may be used to identify the main effects and interactions most significant on a response of a system. However, traditional approaches for screening are ineffective for complex systems because of the size of the experimental design. Consequently, the factors considered are often restricted, but this automatically restricts the interactions that may be identified as well. Alternatively, the designs are restricted to only identify main effects, but this then fails to consider any possible interactions of the factors.
To address this problem, a specific combinatorial design termed a locating array is proposed as a screening design for complex systems. Locating arrays exhibit logarithmic growth in the number of factors because their focus is on identification rather than on measurement. This makes practical the consideration of an order of magnitude more factors in experimentation than traditional screening designs.
As a proof-of-concept, a locating array is applied to screen for main effects and low-order interactions on the response of average transport control protocol (TCP) throughput in a simulation model of a mobile ad hoc network (MANET). A MANET is a collection of mobile wireless nodes that self-organize without the aid of any centralized control or fixed infrastructure. The full-factorial design for the MANET considered is infeasible (with over 10^{43} design points) yet a locating array has only 421 design points.
In conjunction with the locating array, a ``heavy hitters'' algorithm is developed to identify the influential main effects and two-way interactions, correcting for the non-normal distribution of the average throughput, and uneven coverage of terms in the locating array. The significance of the identified main effects and interactions is validated independently using the statistical software JMP.
The statistical characteristics used to evaluate traditional screening designs are also applied to locating arrays.
These include the matrix of covariance, fraction of design space, and aliasing, among others. The results lend additional support to the use of locating arrays as screening designs.
The use of locating arrays as screening designs for complex engineered systems is promising as they yield useful models. This facilitates quantitative evaluation of architectures and protocols and contributes to our understanding of complex engineered networks.
Homeless individuals encounter barriers such as lack of health insurance, increased cost of care and unavailability of resources. They have increased risk of comorbid physical disease and poor mental health. Depression is a prevalent mental health disorder in the US linked to increased risk of mortality. Literature suggests depression screening can identify high-risk individuals with using the patient health questionnaire (PHQ-9).
The objective of this project is to determine if screening identifies depression in the homeless and how it impacts healthcare access. Setting is a local organization in Phoenix offering shelter to homeless individuals. An evidence-based project was implemented over two months in 2019 using convenience sampling. Intervention included depression screening using the PHQ-9, referring to primary care and tracking appointment times. IRB approval obtained from Arizona State University, privacy discussed, and consent obtained prior to data collection. Participants were assigned a random number to protect privacy.
A chart audit tool was used to obtain sociodemographics and insurance status. Descriptive statistics used and analyzed using Intellectus. Sample size was (n = 18), age (M = 35) most were White-non-Hispanic, 44% had a high school diploma and 78% were insured. Mean score was 7.72, three were previously diagnosed and not referred. Three were referred with a turnaround appointment time of one, two and seven days respectively. No significant correlation found between age and depression severity. A significant correlation found between previous diagnosis and depression severity. Attention to PHQ-9 varied among providers and not always addressed. Future projects should focus on improving collaboration between this facility and providers, increasing screening and ensuring adequate follow up and treatment.