Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/41111
Title: Efficient memoization for dynamic programming with ad-hoc constraints
Authors: Jaffar, J. 
Santosa, A.E. 
Voicu, R. 
Issue Date: 2008
Source: Jaffar, J.,Santosa, A.E.,Voicu, R. (2008). Efficient memoization for dynamic programming with ad-hoc constraints. Proceedings of the National Conference on Artificial Intelligence 1 : 297-303. ScholarBank@NUS Repository.
Abstract: We address the problem of effective reuse of subproblem solutions in dynamic programming. In dynamic programming, a memoed solution of a subproblem can be reused for another if the latter's context is a special case of the former. Our objective is to generalize the context of the memoed subproblem such that more subproblems can be considered subcases and hence enhance reuse. Toward this goal we propose a generalization of context that 1) does not add better solutions than the subproblem's optimal, yet 2) requires that subsumed sub-problems preserve the optimal solution. In addition, we also present a general technique to search for at most k ≥ 1 optimal solutions. We provide experimental results on resource-constrained shortest path (RCSP) benchmarks and program's exact worst-case execution time (WCET) analysis. Copyright © 2008, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Source Title: Proceedings of the National Conference on Artificial Intelligence
URI: http://scholarbank.nus.edu.sg/handle/10635/41111
ISBN: 9781577353683
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

62
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.