University of Houston
Department of Computer Science

In partial fulfillment of the Requirements for the Degree of
Doctor of Philosophy
Jing Liu

will defend her dissertation proposal

New Sequential and Parallel Combinatorial Optimization Algorithms with Emphasis on the Traveling Salesman Problem

Abstract
The Traveling Salesman Problem is a classic problem in the field of graph theory and combinatorial optimization.  The problem has been appealing because of its wealth of applications and also because it serves as a test for many combinatorial optimization algorithms.  The Traveling Salesman Problem is an NP-hard problem and it is extremely unlikely we will find an exact solution within polynomial time.  People have been approaching the problem from different angles.  Despite numerous attempts, there is room for improvement in the speed and the quality of the approximation solutions.  At the same time, the rapid advancement of parallel computation techniques gives us exciting new perspectives on this problem.  Parallel computation, in combination with a good algorithm, gives us enormous computational power needed to solve large scale problems.  Compared to many sequential algorithms which are limited by the resources of a single computer, well designed parallel algorithms usually scale very well with minimal modification.  Our proposed research is to explore new sequential and parallel algorithms for combinatorial optimization problems.  The algorithms should have the following desired properties: providing good quality solution; having relatively low complexity; fitting in a parallel computation paradigm and scaling well.  The specific aims of the research include: 1) to study and implement new algorithm(s); 2) to experiment on the standard benchmarks and to compare with existing algorithms in terms of solution quality, speed, resource usage, and scalability; 3) to apply the algorithm(s) on real life cases and analyze the solution.  

Date: Friday, February 17, 2006
Time: 2:00 PM
Place: 515-PGH

Faculty, students, and the general public are invited.
Thesis Advisor: Dr. Olin Johnson