Page 529 - Discrete Mathematics and Its Applications

508 8 / Advanced Counting Techniques

introduced by the mathematician Richard Bellman in the 1950s. Bellman was working at the
RAND Corporation on projects for the U.S. military, and at that time, the U.S. Secretary of
Defense was hostile to mathematical research. Bellman decided that to ensure funding, he
needed a name not containing the word mathematics for his method for solving scheduling and
planning problems. He decided to use the adjective dynamic because, as he said “it’s impossible
to use the word dynamic in a pejorative sense” and he thought that dynamic programming was
“something not even a Congressman could object to.”
AN EXAMPLE OF DYNAMIC PROGRAMMING The problem we use to illustrate dynamic
programming is related to the problem studied in Example 7 in Section 3.1. In that problem
our goal was to schedule as many talks as possible in a single lecture hall. These talks have
preset start and end times; once a talk starts, it continues until it ends; no two talks can proceed
at the same time; and a talk can begin at the same time another one ends. We developed a
greedy algorithm that always produces an optimal schedule, as we proved in Example 12 in
Section 5.1. Now suppose that our goal is not to schedule the most talks possible, but rather to
have the largest possible combined attendance of the scheduled talks.
We formalize this problem by supposing that we have n talks, where talk j begins at
time t j , ends at time e j , and will be attended by w j students. We want a schedule that maximizes
the total number of student attendees. That is, we wish to schedule a subset of talks to maximize
the sum of w j over all scheduled talks. (Note that when a student attends more than one talk, this
student is counted according to the number of talks attended.) We denote by T(j) the maximum
number of total attendees for an optimal schedule from the first j talks, so T (n) is the maximal
number of total attendees for an optimal schedule for all n talks.
We first sort the talks in order of increasing end time. After doing this, we renumber the
talks so that e 1 ≤ e 2 ≤ ··· ≤ e n . We say that two talks are compatible if they can be part of the
same schedule, that is, if the times they are scheduled do not overlap (other than the possibility
one ends and the other starts at the same time). We define p(j) to be largest integer i, i< j,
for which e i ≤ s j , if such an integer exists, and p(j) = 0 otherwise. That is, talk p(j) is the
talk ending latest among talks compatible with talk j that end before talk j ends, if such a talk
exists, and p(j) = 0 if there are no such talks.

RICHARD BELLMAN (1920–1984) Richard Bellman, born in Brooklyn, where his father was a grocer,
spent many hours in the museums and libraries of New York as a child. After graduating high school, he
studied mathematics at Brooklyn College and graduated in 1941. He began postgraduate work at Johns Hopkins
University, but because of the war, left to teach electronics at the University ofWisconsin. He was able to continue
his mathematics studies at Wisconsin, and in 1943 he received his masters degree there. Later, Bellman entered
Princeton University, teaching in a special U.S. Army program. In late 1944, he was drafted into the army. He
was assigned to the Manhattan Project at Los Alamos where he worked in theoretical physics. After the war, he
returned to Princeton and received his Ph.D. in 1946.
After briefly teaching at Princeton, he moved to Stanford University, where he attained tenure. At
Stanford he pursued his fascination with number theory. However, Bellman decided to focus on mathematical questions arising from
real-world problems. In 1952, he joined the RAND Corporation, working on multistage decision processes, operations research
problems, and applications to the social sciences and medicine. He worked on many military projects while at RAND. In 1965 he
left RAND to become professor of mathematics, electrical and biomedical engineering and medicine at the University of Southern
California.
In the 1950s Bellman pioneered the use of dynamic programming, a technique invented earlier, in a wide range of settings. He
is also known for his work on stochastic control processes, in which he introduced what is now called the Bellman equation. He
coined the term curse of dimensionality to describe problems caused by the exponential increase in volume associated with adding
extra dimensions to a space. He wrote an amazing number of books and research papers with many coauthors, including many on
industrial production and economic systems. His work led to the application of computing techniques in a wide variety of areas
ranging from the design of guidance systems for space vehicles, to network optimization, and even to pest control.
Tragically, in 1973 Bellman was diagnosed with a brain tumor. Although it was removed successfully, complications left him
severely disabled. Fortunately, he managed to continue his research and writing during his remaining ten years of life. Bellman
received many prizes and awards, including the first Norbert Wiener Prize in Applied Mathematics and the IEEE Gold Medal of
Honor. He was elected to the NationalAcademy of Sciences. He was held in high regard for his achievements, courage, and admirable
qualities. Bellman was the father of two children.