Project presentations for CSI5165 Combinatorial Algorithms
Room: LPR 285 (Louis Pasteur) - Thursday April 9, 8:50am-12:05
Coffee and donuts will be served.
- 8:50- 9:10 Yiorgos Tzanakis, "A tabu search for Costas arrays"
- 9:15- 9:35 David Thomson, "Heuristic search for low complexity normal bases"
- 9:40-10:00 Mehdi Karimi, "Cycle Enumeration for LDPC codes"
- 10:05-10:25 Katherine Jarvis, "Solving the Subset Sum Problem Using Basis Reduction"
- 10:30-10:50 John Howat, "Minimal Change Ordering for Binary Trees and Triangulations"
- 10:55-11:15 Maryam Haghighi, "Simulated Annealing for a Max-k-weighted max-clique on a Genome Network with DCJ Distance"
- 11:20-11:40 Jose Gonzalez Barrameda, "Genetic Algorithm approach for Channel Assignment problem in Wireless Mesh Networks"
- 11:45-12:05 David Forrester, "Solving The Exact Cover Problem Using Dancing Links"
Abstracts
Title: A tabu search for Costas arrays
Speaker: Yiorgos Tzanakis
A Costas Array of order n is a subset C of size n of the n^2 lattice points
(i,j) with 1<=i,j<=n
such that no two of the n lattice points in C are in the same row and column
and such that
no two of the (n choose 2) line segments between pairs of points agree on
both magnitude
and slope. These are useful in applications such as radar and sonar.
Generation methods
exist and produce Costas Arrays of order n for infinitely many n, but not
for all n. Finding
Costas Arrays has proven to be a remarkably difficult task. We propose a
tabu search
algorithm to search for Costas Arrays of order 32 and 33, for which no
Costas Array is
currently known.
Title: Heuristic search for low complexity normal bases.
Speaker: David Thomson
The efficient implementation of binary arithmetic is highly required in
such areas as cryptography and signal processing. In a normal basis the
operation of squaring has negligible cost, and so exponentiation can be
performed very quickly using the square-and-multiply method. For
efficient communications it is desirable to use normal bases with low
complexity. We present a heuristic search for low complexity normal
bases and compare this to a naive random method. We use a previous
algorithm by the authors (and others) based on a binary Gray code to
efficiently iterate the search.
Title : Cycle Enumeration for LDPC codes
Speaker: Mehdi Karimi
Low Density Parity Check (LDPC) codes are one of the best current channel
codes. The finite-length analysis of LDPC codes is an active area of
research with many open problems. One method to estimate the performance
of finite length LDPC codes is to enumerate all short cycles and check if
these cycles can cause the problem to the decoder. We will present a
cycle enumeration algorithm for enumerating cycles in the graph of a LDPC
code. Our algorithm is based on backtracking algorithm and we have used a
minimum distance criterion to prune it. The results show that this
criterion can improve the efficiency of backtracking algorithm for many
LDPC codes.
Title: Solving the Subset Sum Problem Using Basis Reduction
Speaker: Katherine Jarvis
Basis reduction can be used as an alternative to backtracking or heuristic searches
for solving various combinatorial search problems. We will look at how basis
reduction can be applied to solve combinatorial problems. In 1982 Lenstra et al.
introduced the LLL basis reduction algorithm. The LLL algorithm can be used to
devise polynomial time solutions to classical problems in computer science. For
instance the LLL algorithm played a major role in breaking knapsack based
cryptosystems which are based on the NP-hard subset sum problem. We will see an
implementation of LLL to solve certain instances the subset sum (or knapsack)
problem.
Title:
Minimal Change Ordering for Binary Trees and Triangulations
Speaker: John Howat
Binary trees are ubiquitous in data structuring problems and are often
structurally manipulated through the use of rotations. We will review the work of
Lucas et al., which provides a minimal change ordering on the binary trees on n
nodes such that two adjacent trees differ by a single rotation. This ordering
will be introduced, discussed, and an implementation of the ordering will be
demonstrated. We will also show how to use this minimal change ordering to
produce a minimal change ordering on the triangulations of convex (n+2)-gons,
where two adjacent triangulations differ by a single edge-flip. An implementation
of this will also be demonstrated.
Title: Simulated Annealing for a
Max-k-weighted max-clique on a Genome Network with DCJ Distance
Speaker: Maryam
Haghighi
Double-cut-and-join (DCJ) is a rearrangement operation on the order of genes
in two genomes. The minimum number of such operations that converts one genome to
another is called the DCJ distance. Our goal is to identify clusters of genomes that
are of maximum distance k from each other.
We review the DCJ operation and an algorithm for finding the DCJ distance. Then we
introduce some common clustering approaches. We define a graph based on the DCJ
distance of genomes, and show that finding the clusters is equivalent to finding a
maximum k-weighted maximum clique in this graph. We study a simulated annealing
approach for this problem, and propose two different heuristic searches. After the
implementation, we compare the efficiency of these methods.
Title: Genetic Algorithm approach for Channel Assignment problem in Wireless
Mesh Networks.
Speaker: Jose Andres Gonzalez Barrameda
A wireless Mesh Network is a mesh topology network of nodes interconnected
using wireless links. Because the physical medium is shared, interference
between near links which use a common radio frequency is a common problem.
This interference can highly degrade the network performance. Thus, in order
to increase the network throughput, it is proposed to equip each node with
several network interfaces, and set them to different channels, so
simultaneous non-interfering communication may be carried out. We propose a
Genetic Algorithm approach for this NP-hard problem, believing that a good
solution is composed by good solutions to network sub-sections.
Title: Solving The Exact Cover Problem Using Dancing Links
Speaker: David Forrester
An exact cover of a set is a set of subsets such that each element in
the original set appears exactly once in exactly one of the subsets.
Many computational problems can be reduced to an exact cover problem.
I will demonstrate an algorithm known as "Algorithm X", which solves the
exact cover problem using recursive, nondeterministic, depth-first,
backtracking. I will also discuss an efficient implementation of this
algorithm, known as "Dancing Links". Finally, I will show how Sudoku
puzzles can be reduced to an exact cover problem, and how Dancing Links
can be used to efficiently solve them.