Speaker: Franc Brglez,
Computer Science, NCSU
Experimental Design, as defined in science and manufacturing, relies on data sets that belong to well-defined equivalence classes. There are three basic steps: (1) selection of an equivalence class of experimental subjects, eligible for treatment, (2) application of two or more treatments to the same class, and (3) statistical evaluation of each treatment effectiveness. In this talk, we consider 'treatments' as algorithms applied to equivalence classes of graphs. The characterization of the proposed classes goes much beyond the properties that can be maintained readily, such as the same size, the same distribution of edges, the same number of connected components, etc.
Experiments with several algorithms, ranging from TSP to graph partitioning and embedding, demonstrate that random unbiased selection of graph instances, even if they are of the same size, maintain the same distribution of edges, etc., induces a graph equivalence class that may not differentiate between merits of two specific algorithms. In this talk we introduce a much more refined classification of graphs, in particular of graphs that are representative of the realistic problems encountered in the field. Only when two algorithms are found statistically indistinguishable on the graph equivalence classes with much tighter classification, can we rest the case for comparison.
This work is motivated by a project whose goal is to introduce a web-based environment for collaborative design and execution of experiments that involve (1) common data sets, (2) distributed participants executing the algorithms on these sets, and (3) problem-specific evalutors that archive and process results of all experiments into common reports for further peer reviews. During the next talk in this seminar series on February 10, Dr. Stallmann will demonstrate the on-going application of experimental design techniques to developing and testing new heuristics for representative NP-hard problems. Publications, datasets, and on-going results of experiments related to this talk are available at:
Host: Matthias Stallmann, Computer Science, NCSU
Colloquia Home Page.