Browse Prior Art Database

Efficient Dynamic Programming Using Quadrangle Inequalities

IP.com Disclosure Number: IPCOM000128908D
Original Publication Date: 1980-Mar-01
Included in the Prior Art Database: 2005-Sep-20
Document File: 8 page(s) / 44K

Publishing Venue

Software Patent Institute

Related People

Yao, F.: AUTHOR [+3]

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 0(n 3 ) steps to 0(n 2 ), a result that was first obtained by Knuth using a different and more complicated argument.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 15% of the total text.

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

©; Xerox Palo Alto Research Center, March, 1980

Efficient Dynamic Programming Using Quadrangle Inequalities

F. Frances Yao

CSL 80 4 MARCH 1980
Abstract: See next page.

A version of this paper will appear in Proceedings of the 1980 ACM Symposium on Theory of Computing, April 1980.

CR Categories: 5.3, 8.3.

Key words and phrases: Binary search tree, convex polygon, dynamic programming, quadrangle inequality, triangle inequality.

XEROX

PALO ALTO RESEARCH CENTER 3333 Coyote Hill Road / Palo Alto / California 94304

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 0(n3) steps to 0(n2), a result that was first obtained by Knuth using a different and more complicated argument.

1. INTRODUCTION.

In the application of a general technique, it is often possible to improve the solution by taking advantage of special properties of the problem at hand. Dynamic programming is one of several widely used problem-solving techniques in computer science and operation research (see, e.g. [ 2 ] ). It finds applications in context-free language parsing [ 8 ] , constructing optimal binary trees 171, finding shortest paths [ 4 ] , and in solving various "intractible" combinatorial problems (see the references in [ 2 ] ). In the construction of optimal binary search trees, for example, Knuth [ 5
] [7 ] showed that an 0(n2) algorithm may be obtained by improving upon the straightforward dynamic programming solution which demanded time 0(n3). Knuth's proof is quite complicated and involves detailed properties of the optimal binary trees. In general, ad hoc approaches for speeding up seem to be characteristic in dynamic programming; few general criteria are known.

In the present paper we will discuss a quadrangle inequality condition for the purpose of achieving speed-up in dynamic programming. This condition is easily checked and will be applied to several apparently different problems. In particular, it is used to give a simple proof of Knuth's construction of optimal trees, and applied to optimization problems involving multiway partitions.

Xerox Corporation Page 1 Mar 01, 1980

Page 2 of 8

Efficient Dynamic Programming Using Quadrangle Inequalities

2. DYNAMIC PROGRAMMING AND QUADRANGLE INEQUALITIES.

We consider a simple dynamic programming problem for the...