TY - GEN
T1 - Separating interaction effects using locating and detecting arrays
AU - Seidel, Stephen A.
AU - Sarkar, Kaushik
AU - Colbourn, Charles
AU - Syrotiuk, Violet
N1 - Funding Information:
This work is supported in part by the U.S. National Science Foundation grant #1421058, and in part by the Software Test & Analysis Techniques for Automated Software Test program by OPNAV N-84, U.S. Navy.
PY - 2018
Y1 - 2018
N2 - The correctness and performance of complex engineered systems are often impacted by many factors, each of which has many possible levels. Performance can be affected not just by individual factor-level choices, but also by interactions among them. While covering arrays have been employed to produce combinatorial test suites in which every possible interaction of a specified number of factor levels arises in at least one test, in general they do not identify the specific interaction(s) that are significant. Locating and detecting arrays strengthen the requirements to permit the identification of a specified number of interactions of a specified size. Further, to cope with outliers or missing responses in data collected from real engineered systems, a further requirement of separation is introduced. In this paper, we examine two randomized methods for the construction of locating and detecting arrays, the first based on the Stein-Lovász-Johnson paradigm, and the second based on the Lovász Local Lemma. Each can be derandomized to yield efficient algorithms for construction, the first using a conditional expectation method, and the second using Moser-Tardos resampling. We apply these methods to produce upper bounds on sizes of locating and detecting arrays for various numbers of factors and levels, when one interaction of two factor levels is to be detected or located, for separation of up to four. We further compare the sizes obtained with those from more targeted (and more computationally intensive) heuristic methods.
AB - The correctness and performance of complex engineered systems are often impacted by many factors, each of which has many possible levels. Performance can be affected not just by individual factor-level choices, but also by interactions among them. While covering arrays have been employed to produce combinatorial test suites in which every possible interaction of a specified number of factor levels arises in at least one test, in general they do not identify the specific interaction(s) that are significant. Locating and detecting arrays strengthen the requirements to permit the identification of a specified number of interactions of a specified size. Further, to cope with outliers or missing responses in data collected from real engineered systems, a further requirement of separation is introduced. In this paper, we examine two randomized methods for the construction of locating and detecting arrays, the first based on the Stein-Lovász-Johnson paradigm, and the second based on the Lovász Local Lemma. Each can be derandomized to yield efficient algorithms for construction, the first using a conditional expectation method, and the second using Moser-Tardos resampling. We apply these methods to produce upper bounds on sizes of locating and detecting arrays for various numbers of factors and levels, when one interaction of two factor levels is to be detected or located, for separation of up to four. We further compare the sizes obtained with those from more targeted (and more computationally intensive) heuristic methods.
UR - http://www.scopus.com/inward/record.url?scp=85049926284&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049926284&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-94667-2_29
DO - 10.1007/978-3-319-94667-2_29
M3 - Conference contribution
AN - SCOPUS:85049926284
SN - 9783319946665
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 349
EP - 360
BT - Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Proceedings
A2 - Leong, Hon Wai
A2 - Iliopoulos, Costas
A2 - Sung, Wing-Kin
PB - Springer Verlag
T2 - 29th International Workshop on Combinatorial Algorithms, IWOCA 2018
Y2 - 16 July 2018 through 19 July 2018
ER -