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....[ Read more ]

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.