Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #6281 > unrolled thread

Speeding up dynamic programming

Back to article view | Back to comp.programming

Contents

  Speeding up dynamic programming Paul <pepstein5@gmail.com> - 2016-03-01 06:50 -0800
    Re: Speeding up dynamic programming Randy Howard <rhoward.mx@EverybodyUsesIt.com> - 2016-03-02 10:12 -0600
      Re: Speeding up dynamic programming Paul <pepstein5@gmail.com> - 2016-03-06 11:43 -0800

#6281 — Speeding up dynamic programming

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

[toc] | [next] | [standalone]

#6282

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/knuthyaotalg.pdf

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)

[toc] | [prev] | [next] | [standalone]

#6298

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/knuthyaotalg.pdf
> 
> 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/p429-yao.pdf  
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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web