Title: More Efficient Dynamic Programming Speedups
Speaker: Mordecai Golin
Date: Friday,  February 24, 2006
Time 11-12 Venue: Room 3464, HKUST   

Abstract 

In this talk we will discuss some very general 
Dynamic Programming Speedup tools along with 
applications.

In particular,  we will 
(i) give a new, simpler, algorithm for Length-Limited 
Huffman Codes, based on a nested Monge matrix formulation 
combined with the SMAWK algorithm

(ii) Show how to extend an old space saving technique 
due to Hirschberg. This will permit decreasing  the 
space needed by the Huuman coding algorithm and also 
decrease the space needed by algorithms given in the 
literature for finding K-medians on a line