Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-042 | 1st March 2018 19:24

Incremental versus Non-Incremental Dynamic Programming

RSS-Feed




TR18-042
Authors: Stasys Jukna
Publication: 1st March 2018 19:25
Downloads: 265
Keywords: 


Abstract:

Many dynamic programming algorithms for discrete optimization problems are "pure" in that they only use min/max and addition operations in their recursions. Some of them, in particular those for various shortest path problems, are even "incremental" in that one of the inputs to the addition operations is a variable. We present an explicit optimization problem such that it can be solved by a pure DP algorithm using a polynomial number of operations, but any incremental DP algorithm for this problem requires a super-polynomial number of operations.



ISSN 1433-8092 | Imprint