you're reading...

Algorithms talk on Friday 22 July

Dear all,

The SACT seminar is back at the same time of 11am, and in the Boardroom as always. Feel free to come along!

Presentation by Andrew Santosa.

Interpolation in Dynamic Programming

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. Using a logical notion of “interpolation,” we propose a generalization of context that 1) does not add better solutions than the subproblem’s optimal, yet 2) requires that subsumed subproblems 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.



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: