EXTENDING THE QUADRANGLE INEQUALITY TO SPEED-UP DYNAMIC-PROGRAMMING

Proving that a function satisfies the quadrangle inequality is a power ful and elegant way to show that a dynamic programming algorithm to co mpute that function can be sped up by a factor of the input size. In t his paper we consider two problems that do not fit in the usual genera l cases of functions that satisfy the quadrangle inequality but for wh ich the proof of the quadrangle inequality still carries through: the multi-peg Tower of Hanoi problem with weighted disks and the problem o f constructing a Rectilinear Steiner Minimal Arborescence (RSMA) on a slide. We prove the quadrangle inequality holds for a generalized func tion that unifies the two problems. This speeds up algorithms for thes e problems from O(n3p) to O(n2p) and from O(n3) to O(n2) respectively.