--------------------------------------------------------
                      NATIONAL  UNIVERSITY  OF  SINGAPORE
                              School of Computing

                              Guest Lecture @CS6204
          --------------------------------------------------------

Date:     Tuesday, 12 Sept 2000
Time:     6.30 pm - 7:30 pm, Tuesday
Venue:    SR2 (S15, Level 4)
 	         	   
Title:    Exhaustive Search, Combinatorial Optimization
          and Enumeration: Exploring the Potential of
          Raw Computing Power
			
Speaker:  Prof Jurg Nievergelt   
          Computer Science
          Swiss Federal Institute of Technology ETH, Zurich

Abstract:

For half a century since computers came into existence, the goal of 
finding elegant and efficient algorithms to solve "simple"
(well-defined and well-structured) problems has dominated algorithm
design. Over the same period, both processing and storage capacity of
computers have increased by roughly a factor of a million. The next few
decades may well give us a similar rate of growth in raw computing
power, due to various factors such as continuing miniaturization,
parallel and distributed computing. If a quantitative change of orders
of magnitude leads to qualitative advances, where will the latter take
place? Only empirical research can answer this question.

Asymptotic complexity theory has emerged as a surprisingly effective
tool for predicting run times of polynomial-time algorithms. For
NP-hard problems, on the other hand, it yields overly pessimistic
bounds. It asserts the non-existence of algorithms that are efficient
across an entire problem class, but ignores the fact that many
instances, perhaps including those of interest, can be solved
efficiently. For such cases, we need a complexity measure that applies
to problem instances, rather than to over-sized problems classes. 

Combinatorial optimization and enumeration problems are modeled by
state spaces that usually lack any regular structure. Exhaustive search
is ofthe nthe only way to handle such "combinatorial chaos". Several
general purpose search algorithms are used under different
circumstances. We describe reverse search and illustrate this technique
on a case study of enumerative optimization: enumerating the k shortest
Euclidean spanning trees.


Biodata:

J. Nievergelt has been a professor of computer science since 
1965 at the University of Illinois, ETH Zurich, and as Dept. Chairman
at the University of North Carolina Chapel Hill. Research interests 
have spanned interactive systems and user interfaces, algorithms and 
data structures, combinatorial optimization and parallel computation.
He is a Fellow of ACM and IEEE.