Department of Systems Engineering and Engineering Management,

                    The Chinese University of Hong Kong


A new perspective into solving
the Traveling Salesman Problem by dynamic programming

Dr. Joaquim A. S. Gromicho
Vrije Universiteit, Amsterdam,
The Netherlands & ORTEC International,
Gouda, The Netherlands

Date : November 16, 2005 (Wednesday)

Time : 5:30 p.m. - 6:30 p.m.

Venue : Room 513, William M.W. Mong Engineering Building

(Engineering Building Complex Phase 2), CUHK

Dynamic programming plays an important role in optimization, and particularly
in combinatorial optimization.

The Traveling Salesman Proble (TSP) is one of the most celebrated of the
NP-hard combinatorial problems, and therefore its lowest complexity is still
unknown. However, dynamic programming offers since the work of Held and Karp
in 1962 the lowest known complexity to the problem. Consequently, Dynamic
Programming has a strong theoretical relevance for the TSP.

The practical relevance of Dynamic Programming when applied to the TSP, or
other NP-hard problems, is perceived as being much smaller.

This talk brings Dynamic Programming into a new perspective. From this
perspective we aim at reviving the approach as a practical and competitive
setting to solve realistic TSP instances in both heuristic and optimal senses.

This is joint work with Aukje van den Hoeven, VU & ORTEC.

Joaquim A. S. Gromicho is a Senior Software Architect at ORTEC Software
Development within ORTEC International and an Assistant Professor at the
Econometrics Department of the Vrije Universiteit in Amsterdam. He received
his Ph.D. from the Erasmus Universiteit Rotterdam and his MSc from the
Universidade de Lisboa. His research interests are on optimization, with a
special emphasis towards Combinatorial Optimization and its applications to


                       ***** ALL ARE WELCOME *****

Host : Prof. Shuzhong Zhang
Tel : 26098240
Email : zhang@se.cuhk.edu.hk

For more information please

refer to http://www.se.cuhk.edu.hk/~seg5810/