Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/3082

Dynamic programming speedups

Authors Zhang, Yan
Issue Date 2007
Summary Dynamic programming 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 Θ(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, 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.
Note Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2007
Subjects
Language English
Format Thesis
Access
Files in this item:
File Description Size Format
th_redirect.html 345 B HTML