Our Backs to the Wall: A Survival Guide for Facing NP-Complete Problems

July 15, 2007

The Research in Computer Science Seminar Presents: Our Backs to the Wall: A Survival Guide for Facing NP-Complete Problems

by: Joshua Geiger and Adam Smith

Abstract

This talk will explore heuristics for two commonly encountered NP-complete problems in the field of regression testing: the minimal feedback vertex set problem and the set cover problem. The task of reducing and prioritizing independent test cases directly reduces to the set cover problem; part of the task of minimizing database restores during regression testing of database-centric applications requires approximating the minimal feedback vertex set problem. We will conclude with a discussion of the relationship between theory and practice in the field of computer science.

Location: Campus Center 318
Date: Friday, July 27, 2007
Time: 12:15 - 1:15

All are welcome to attend!