Type of Talk: Colloquium

Speaker Name: Jian

er Chen

Speaker Affiliation: Professor in Computer Science Texas A

&M University

Date: Friday February 16 2007

Start Time: 11:

00 a.m.
Coffee 10:45 am.

Location: TAY 3.128

Host: Vijaya

Ramachandran

Talk Title:Improved Algorithms for Path Matching & Pac

king Problems

Talk Abstract:
Improved randomized and deterministi

c algorithms are presented
for well-known NP-hard Path Matching and P

acking problems. Our
randomized algorithms are based on the divide-and-

conquer technique
and improve previous best algorithms for these probl

ems. For example
for the k-Path problem our randomized algorithm runs
in time $O(4%5Ek k%5E%7B2.7%7Dm)$ and space $O(nk%5Clog k + m)$ improving
the previous best randomized algorithm for the problem that runs in time $

O(5.44%5Ekkm)$
and space $O(2%5Ek k n + m)$. To achieve improved determ

inistic algorithms we study a number of previously proposed derandomizatio

n schemes and show how they can be improved and effectively used to achiev

e efficient deterministic algorithms. This study results in the following d

eterministic algorithms: one of time $O(4%5E%7Bk+o(k)%7Dm)$ for
the k-P

ath problem one of time $O(2.80%5E%7B3k%7Dk n %5Clog%5E2 n)$ for the 3-D m

atching problem and one of time $O(3.2%5E%7B3k%7Dn)$ for the 3-Set Packing
problem. All these significantly improve previous best deterministic algor

ithms for the problems.

* This is a joint work with S. Lu S.-H. Sze
and F. Zhang

Speaker Bio:
Jianer Chen got his Ph.D. in Compute

r Science from Courant Institute of Mathematical Sciences NYU and his Ph.

D. in Mathematics
from Columbia University. Currently he is a professor

in computer
science at Texas A&M University. His research interests incl

ude
algorithms and optimization computer graphics and computer.