WHAT:  Computer Science Master Thesis Presentation by
           Sammy Raymond D'Souza
           on Parallelizing a Non-Deterministic Optimization Algorithm
WHEN: April 27 (Friday), 1- 2 PM
WHERE:  JB 389/391 (Math Conference Room)

ADVISOR:  Dr. Ernesto Gomez
COMMITTEE:  Dr. Keith Schubert, Dr. Tong Lai Yu

ABSTRACT:

The traditional view of algorithmic efficiency is that the total work done
in a parallel execution (across all nodes) cannot be less than in its 
serial counterpart. However, in a parallel run, execution results are 
available at different times and in a different sequence. It is therefore 
possible for any one node to shortcut others and thereby achieve higher 
parallel efficiencies. This research explores the idea that for certain 
optimization problems there is a way to parallelize the algorithm such that
the parallel efficiency can exceed one hundred percent. Specifically, a 
parallel compiler, PC, is used to apply shortcutting techniques to a 
metaheuristic, Ant Colony Optimization (ACO), to solve the well-known 
Traveling Salesman Problem (TSP) on a cluster running MPI. The results of 
both serial and parallel execution are compared, with test datasets from 
TSPLIB. Directions for future work are cited.