PhD Thesis Proposal Defence


"Dynamic Programming Speedups"

by

Mr. Yan Zhang


Abstract:

Dynamic programming (DP) is a standard technique used in optimization. It
is well known that if a dynamic program possesses what is known as a
'Monge property' its solution can be improved.  For example, by showing
the existence of a Monge property, some very common forms of dynamic
programs can be sped up by a factor of Theta(n). Surprisingly, the Monge
property appears quite naturally in many applications (since it is
essentially the discrete realization of a form of concavity). For example,
problems in a range of areas, including computational geometry,
bioinformatics, VLSI design, networking, multimedia, etc. have all been
shown to possess this property.

In this thesis proposal we consider various issues surrounding Monge
speedups that do not seem to have been addressed before, e.g.,
space-saving and modifications so that the speedup works in online
settings.  We also show its relation to other forms of dynamic programming
speedups that previously seemed to be unconnected to the Monge one.


Date:     		Wednesday, 6 December 2006

Time:                   2:00p.m.-4:00p.m.

Venue:                  Room 3315
			lifts 17-18

Committee Members:      Dr. Mordecai Golin (Supervisor)
                        Dr. Nevin Zhang (Chairperson)
			Dr. Brahim Bensaou
			Dr. Chin Tau Lea (ECE)


**** ALL are Welcome ****