Efficient dynamic programming using quadrangle inequalities

ABSTRACT

Dynamic programming is one of several widely used problem-solving techniques in computer science and operation research. In applying this technique, one always seeks to find speed-up by taking advantage of special properties of the problem at hand. However, in the current state of art, ad hoc approaches for speeding up seem to be characteristic; few general criteria are known. In this paper we give a quadrangle inequality condition for rendering speed-up. This condition is easily checked, and can be applied to several apparently different problems. For example, it follows immediately from our general condition that the construction of optimal binary search trees may be speeded up from O(n3) steps to O(n2), a result that was first obtained by Knuth using a different and rather complicated argument.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: K. Q. Brown, Dynamic programming in computer science, Computer Science Department Report CMU-CS-79-106, Carnegie-Mellon University, February 1979.
• 3: D. P. Dobkin and L. Snyder, On a general method for maximizing and minimizing among certain geometric problems, Proc. IEEE 20th Annual Symposium on Foundations of Computer Science, Puerto Rico, 1979, 9–17.
• 4: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 5: D. E. Knuth, Optimum binary search trees, Acta Informatica 1 (1971), 14–25.
• 6: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 7: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 8: D. H. Younger, Recognition of context-free languages in time n3, Information and Control 10 (1967), 189–208.
• 9: Y. Zhu and J. Wang, On alphabetic-extended binary trees with restricted path length, Scientia Sinica22 (1979), 1362–1371.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Theory