Project Presentation: CSI7160 Combinatorial Algorithms and Structures 

Friday November 29, 2002
Room: CBY 202 (usual classroom)
-------------------------------------------------------------------------
10:00 Hughes Chataing, 
      "Simulated annealing solutions for the Traveling Salesman Problem"
10:30 Sebastian Raaphorst, "Branch-and-Cut with Isomorphism Pruning"
11:00 Ariane Masuda, "A search for suboptimal normal elements 
      in finite fields without optimal normal elements."
11:30 Ming Xie, "Checking Cycle Symmetric Graph with Exhaustive Algorithm"
12:00 Karen Meagher, "Non-isomorphic Generation of Covering arrays"
12:30 Misha Jiline, "Combinatorial Algorithms for Sequencing by
      Hybridization(SHB)"          
-------------------------------------------------------------------------
13:00-14:00 joint lunch (at SITE cafeteria, buy there or bring your own)
-------------------------------------------------------------------------
14:00 Alan Martin, "Digital Halftoning by Heuristic Search"
14:30 Kevin Lam, "A mini-max selection algorithm for two-player games"
15:00 Zhenglin Jin,  "Finding max sub-graph of two Conceptual Graphs"
15:30 Thierry Metais, "A recursive clustering approach for the TSP"
-------------------------------------------------------------------------

Abstracts:

"Simulated annealing solutions for the Traveling Salesman Problem",
Hugues Chataing,
My project consists on implementing different versions of simulated 
annealing algorithm (taken from literature or not) to solve the T.S.P.
Thus I will be able to compare the efficiency of those algorithms. The
comparison are made with graphs taken from the TSPLIB, in order to compare
my results to actual results.

"Branch-and-Cut with Isomorphism Pruning", Sebastian Raaphorst,
Many problems, specifically in combinatorics, demonstrate a large 
number of symmetries or isomorphisms. Branch-and-Cut can be a feasible 
method for solving these types of problems, but may be infeasible for 
moderate sized instances due to the large number of isomorphic 
subproblems. By pruning these subproblems, we can avoid unnecessary 
computation.

"A search for suboptimal normal elements in finite fields without 
optimal normal elements", Ariane Masuda,
A normal element in a finite field F_{q^n} over F_q is said to be 
optimal if its complexity is exactly 2n-1. All finite fields have normal 
elements, but not all of them have optimal normal elements. We are 
interested on investigating the low complexity normal elements when
there is no optimal normal element.

"Checking Cycle Symmetric Graph with Exhaustive Algorithm", Ming Xie,
Cycle symmetricity is related to the notion of "minimal sense of 
direction" which is useful in distributed computing. It is a necessary 
condition for minimum sense of direction in regular graph. In the
project, we study the application of cycle symmetricity and its properties, 
and develop an exhaustive algorithm to check if a given graph is
cycle symmetric.

"Non-isomorphic Generation of Covering arrays", Karen Meagher
I will give the definition of covering arrays and explain what it means 
for such arrays to be isomorphic. I will explain a backtracking program I 
have writen that produces all non-isomorphic covering arrays of a given size. 
Finally I will show some results and outline further work that needs to be 
done on the program.

"Finding max sub-graph of two Conceptual Graphs", Zhenglin Jin
Human languages can be represented by Conceptual Graphs(CG). To measure 
the similarity of two given sentences, we can construct CG for each of 
them and find their Maximum Common Subgraph(MCS). This project solves this 
problem by constructing an Association Graph(AG) for the given two CGs and 
search for the max clique of the AG.

"Digital Halftoning by Heuristic Search", Alan Martin,
Halftoning is the process by which dots of ink are placed to form an image.
There are well-known algorithms for this but they have various defects.
My project consists of applying the methods of heuristic search to try to
develop a halftoning algorithm that gives better results in reasonable time.

"A mini-max selection algorithm for two-player games", Kevin Lam
(Abstract TBA)

"Combinatorial Algorithms for Sequencing by Hybridization(SHB)", 
Misha Jiline, 
String reconstruction problem may be formulated and solved in
terms of different mathematical theories. The most popular approach is
dynamic programming. However, combinatorial algorithms may be also
applicable for string reconstruction. This presentation describes three
combinatorial algorithms used in Sequencing by Hybridization (SHB)
approach to DNA sequencing.

"A recursive clustering approach for the TSP", Thierry Metais, 
This approach consists in solving the main problem by solving smaller instances.
First we will try to cluster the cities into several clusters with an
acceptable number of cities. We will then solve the TSP for the different
clusters and finally link all the partial solutions to get the global solution.