Symantec - Science Buddies Special Award in Computer Science, 2010 Winner
Name: Michael Yurko
School: Detroit Catholic Central High School, Novi, Michigan
Project Title: "A Parallel Computational Framework for Solving Quadratic Assignment Problems Exactly"
Overview: The main subject of my project is the quadratic assignment problem (QAP). QAPs are a class of mathematical problems that can be used to model many situations involving network flows, including applications in the design of circuitry and placement of facilities. However, QAPs are also very computationally difficult to solve. In the worst case the time it takes to solve is exponential in size of the QAP. My project implemented the first freely available solver for QAPs. It is also a parallel framework meaning that it runs across computers with many CPUs. The results of the solver were promising. It was able to solve a QAP of size 25 in about 50 minutes on a computer with 24 processors. Previously, the largest scale effort used a state of the art solver to solve a QAP of size 30 in a week on a supercomputing grid with thousands of computers.