[lnkForumImage]
TotalShareware - Download Free Software

Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.programming

Speeding up dynamic programming

Paul

3/1/2016 2:51:00 PM

I'm interested in the question of how and when naive dynamic programming techniques can be speeded up. One example is when the quadrangle inequality holds but that is a fairly restricted condition. Can anyone point me to a summary of elementary techniques which hold more widely? Thank you,

Paul
2 Answers

Randy Howard

3/2/2016 4:12:00 PM

0

On 3/1/16 8:50 AM, Paul wrote:
> I'm interested in the question of how and when naive dynamic
> programming techniques can be speeded up. One example is when
> the quadrangle inequality holds but that is a fairly restricted
> condition. Can anyone point me to a summary of elementary
> techniques which hold more widely? Thank you,
>
> Paul

From the terms used above, it seems likely that you've already read
the paper "The Knuth-Yao Quadrangle-Inequality Speedup is a
Consequence of Total-Monotonicity" by Bein, Golin, Larmore & Zhang.
If not you might want to look at this:
http://www.egr.unlv.edu/~bein/pubs/knuthy...

Exploring the references at the end of the paper will perhaps also
be of some benefit.

--
Randy Howard
(replace the obvious text in the obvious way if you wish to contact me
directly)

Paul

3/6/2016 7:43:00 PM

0

On Wednesday, March 2, 2016 at 4:12:16 PM UTC, Randy Howard wrote:
> On 3/1/16 8:50 AM, Paul wrote:
> > I'm interested in the question of how and when naive dynamic
> > programming techniques can be speeded up. One example is when
> > the quadrangle inequality holds but that is a fairly restricted
> > condition. Can anyone point me to a summary of elementary
> > techniques which hold more widely? Thank you,
> >
> > Paul
>
> From the terms used above, it seems likely that you've already read
> the paper "The Knuth-Yao Quadrangle-Inequality Speedup is a
> Consequence of Total-Monotonicity" by Bein, Golin, Larmore & Zhang.
> If not you might want to look at this:
> http://www.egr.unlv.edu/~bein/pubs/knuthy...
>
> Exploring the references at the end of the paper will perhaps also
> be of some benefit.

Thanks a lot for this recommendation. You overestimate me, I'm afraid. All I read was Yao's paper on the quadrangle inequality -- http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/p4...
I look forward to reading the SMAWK paper (which I don't know at all) and then I hope to move on to your reference.

Paul