HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Doctoral Theses >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/3082
Title: Dynamic programming speedups
Authors: Zhang, Yan
Issue Date: 2007
Abstract: 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.
Description: Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2007
ix, 101 leaves : ill. ; 30 cm
HKUST Call Number: Thesis CSED 2007 ZhangY
URI: http://hdl.handle.net/1783.1/3082
Appears in Collections:CSE Doctoral Theses

Files in This Item:

File Description SizeFormat
th_redirect.html0KbHTMLView/Open

All items in this Repository are protected by copyright, with all rights reserved.