Gregory M. Kapfhammer

Efficient Time-Aware Prioritization with Knapsack Solvers

Sara Alspaugh, Kristen R. Walcott, Michael Belanich, Gregory M. Kapfhammer, and Mary Lou Soffa. Efficient Time-Aware Prioritization with Knapsack Solvers. In the Proceedings of the ACM International Workshop on Empirical Assessment of Software Engineering Languages and Technologies, Atlanta, Georgia, November 2007.

Related Projects: Kanonizo

Abstract

Regression testing is frequently performed in a time constrained environment. This paper explains how 0/1 knapsack solvers (e.g., greedy, dynamic programming, and the core algorithm) can identify a test suite reordering that rapidly covers the test requirements and always terminates within a specified testing time limit. We conducted experiments that reveal fundamental trade-offs in the (i) time and space costs that are associated with creating a reordered test suite and (ii) quality of the resulting prioritization. We find knapsack-based prioritizers that ignore the overlap in test case coverage incur a low time overhead and a moderate to high space overhead while creating prioritizations exhibiting a minor to modest decrease in effectiveness. We also find that the most sophisticated 0/1 knapsack solvers do not always identify the most effective prioritization, suggesting that overlap-aware prioritizers with a higher time overhead are useful in certain testing contexts.

[PDF] [PS] [BibTeX Entry] [Copyright Notice]

---

Links to this Page

• Complete News Listing last edited on 21 October 2009 at 5:22 pm by 141.195.226.29
• Kanonizo last edited on 21 October 2009 at 5:06 pm by 141.195.226.29
• Research Papers last edited on 20 October 2009 at 5:41 pm by 141.195.226.29
• Efficient Time-Aware Prioritization with Knapsack Solvers last edited on 21 May 2008 at 2:19 pm by aldenv29.allegheny.edu