Accelerating Dynamic Programming

Dynamic Programming (DP) is a fundamental problem-solving technique that has been widely used for solving a broad range of search and optimization problems. While DP can be invoked when more specialized methods fail, this generality often incurs a cost in ef ciency. We explore a toolkit for speeding up DP, and algorithms that use DP as subroutines. The toolkit includes: - Acceleration via Compression - Totally Monotone Matrice - Combining Compression and Total Monotonicity - Partial Tables - Fractional Subproblems

Autorentext

Oren Weimann is a post-doctoral fellow in the Department of Computer Science and Applied Mathematics at Weizmann Institute of Science. He received his Ph.D. from the Computer Science and Artificial Intelligence Laboratory (CSAIL) in Massachusetts Institute of Technology.