NC State University

Department of Computer Science Colloquia 1999-2000

Date: Thursday, January 20, 2000
Time: 3: 30 PM (refreshments), 4:00 PM (talk)
Place: Withers 402A, NCSU Historical Campus (click for courtesy parking request )

Speaker: Franc Brglez, Computer Science, NCSU

Evaluating the Performance of Heuristics for NP-hard Problems: Are We Ready for a New Treatment?

Abstract: More than a thousand mathematical problems arising in engineering and science have been shown to be NP-hard. There is no shortage of published claims of `incremental improvements' with a particular heuristic. However, such claims may well be subject to undocumented experimental errors, and have not been supported by a rigorous statistical analysis, including a test of hypothesis such as `Is the improvement due to the choice of the algorithm or due to chance?'

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:

Short Bio: See the home page under Franc Brglez.

Host: Matthias Stallmann, Computer Science, NCSU

Colloquia Home Page.