From Dynamic Programming to Greedy Algorithms

Richard Bird and Oege de Moor^{⋆}

Programming Research Group 11 Keble Road Oxford OX1 3QD United Kingdom

Abstract A calculus of relations is used to reason about specifications and algorithms for optimisation problems. It is shown how certain greedy algorithms can be seen as refinements of dynamic programming. Throughout, the maximum lateness problem is used as a motivating example.

1 Introduction

An optimisation problem can be solved by dynamic programming if an optimal solution is composed of optimal solutions to subproblems. This property, which is known as the principle of optimality, can be formalised as a monotonicity condition. If the principle of optimality is satisfied, one can compute a solution by decomposing the input in all possible ways, recursively solving the subproblems, and then combining optimal solutions to subproblems into an optimal solution for the whole problem. By contrast, a greedy algorithm considers only one decomposition of the argument. This decomposition is usually unbalanced, and greedy in the sense that at each step the algorithm reduces the input as much as possible. If the decomposition has a more balanced character, the algorithm is commonly classified as an instance of the divide–and–conquer paradigm.

Certain greedy algorithms can be seen as refinements of dynamic programming. If the principle of optimality is satisfied, dynamic programming is applicable, and if an additional monotonicity condition is satisfied, then we can narrow the choice of decompositions to a single candidate, thus obtaining a greedy algorithm. This idea was formalised in [3] for a restricted class of optimisation problems, namely those involving list partitions. Although it was suggested that the technique might be more widely applicable, it proved difficult to formulate the general theorem in the framework of that paper. The conclusion was that a more flexible framework was needed, and this observation motivated one of us to undertake an in–depth study of dynamic programming in a categorical setting [15]. The present paper summarises the results on dynamic programming, and shows how they can be extended to a theory of greedy algorithms.

The structure of the paper is as follows. First we study a typical application of the greedy strategy, the so–called maximum lateness problem from operations research. This example serves to explain the objectives of the paper and provides motivation for the

⋆ Research supported by a studentship from British Petroleum International.

subsequent calculus. After introducing this calculus, we show how dynamic programming applies to the problem. We then go on to prove an abstract result about greedy algorithms, and show how a greedy algorithm can be derived for our example. We conclude with a brief discussion of the implications of the research.

2 Example: Maximum Lateness

Maximum Lateness is a scheduling problem: given a bag x of jobs, we want to find a permutation y, called a schedule, of x that minimises a certain function c, called the cost function. This cost function returns the so-called maximum lateness of a schedule, and this explains the name of the problem [7]. The maximum lateness problem is specified as a relation mt, where

mt = min(c) · perms.

The function perms returns the set of all permutations of a bag. That is,

perms y = { x | bagify x = y },

where bagify is the function that turns a sequence of jobs into a bag. The relation min(c) holds between a set of schedules and those of minimum cost c:

y (min(c)) ys = y ∈ ys ∧ (∀z ∈ ys : c y ≤ c z).

The cost function c returns the maximum lateness of a schedule. With each job a are associated three nonnegative quantities: a processing time time a, a due time due a, and a weight weight a. The processing time is a measure of the relative time it takes to complete a job. The due time gives the absolute time when a job should be finished. Finally, the weight of a job indicates the importance of finishing this job in time. An important job has a high weight, and an unimportant one a low weight.

The cost function is defined by the following equations (we write (++) for concatenation of sequences and [a] for the singleton sequence with element a)

c y = max { lateness z | ∃v : z ++ v = y ∧ z ≠ [ ] }
lateness (z ++ [a]) = weight a × (length (z ++ [a]) − due a)
length z = ∑_{a∈z}(time a).

In words, the length of a (partial) schedule is the total time taken to complete it, which is the sum of the individual processing times. The lateness of a job a coming after a partial schedule z is a weighted measure of the time by which length (z ++ [a]) exceeds the due time of a (a negative quantity if a is completed before it is due). Finally, the cost of a schedule is the maximum, taken over all nonempty prefixes z of the schedule, of the lateness associated with z.

We can also define the cost c recursively by the equations (writing [ ] for the empty sequence)

c [ ] = −∞
c(y ++ [a]) = c y ⊔ ((bagify y) ⊗ a)
y ⊗ a = wt a × (∑_{b∈y}(time b) + time a − due a).

Here (⊔) stands for the binary operator that returns the maximum of its arguments. We have defined y ⊗ a for a bag y rather than a list, because the order of elements is unimportant. This observation will be useful when we derive an efficient algorithm for mt.

An example. The table below displays an instance of the maximum lateness problem. There are four jobs given, named a, b, c and d. The respective values of time, due and weight are given in the subsequent columns. The minimum cost of a schedule is 20, and this minimum is realized by two schedules: bcda and cbda.

name time due weight
a  10 13  4
b  3 3  5
c  1 2  6
d  4 5  3

Dynamic programming solution. A typical dynamic programming solution for the maximum lateness problem is given by

mt x = \{ \begin{matrix}[ ], & if x = ⟨ ⟩ \\ min(c)\{mt y ++ [a] | y + ⟨a⟩ = x\}, & otherwise \end{matrix}

Here we use ⟨ ⟩ to denote the empty bag, ⟨a⟩ for the singleton bag with element a, and + for bag union. This dynamic programming solution for mt takes time exponential in the size of x, even when the recursive calls of mt are tabulated. Admittedly, this description of dynamic programming is informal, since the notation suggests that mt is a function while it is really a relation. To give a rigorous formulation, we shall need various concepts from the relational calculus, which will be introduced in Section 3 below.

Greedy solution. The greedy algorithm for maximum lateness can be described by the following recursion equation:

mt x = \{ \begin{matrix}[ ], & if x = ⟨ ⟩ \\ mt y ++ [a], & otherwise. \\ where (y, a) = split x. \end{matrix}

The expression split x yields a pair (y, a), consisting of a bag y and an element a such that y + ⟨a⟩ = x. Furthermore, y and a are chosen to minimise the value of y ⊗ a. In this sense, the algorithm is greedy: split finds an optimal splitting. A straightforward implementation of the greedy algorithm takes cubic time: it takes quadratic time to find the optimum split, because there is a linear number of splits (y, a), and one may compute y ⊗ a in linear time. Using well-known program transformations, this naive program can be transformed into a quadratic time program, thus obtaining Lawler’s algorithm [10]. There is a yet more efficient implementation of the same greedy strategy, which only requires O(n log^{2} n) computation steps [7].

The general questions we are interested in are these: how is the dynamic programming solution derived from the initial problem statement, and what extra conditions are necessary to ensure that a greedy algorithm also solves the problem? To answer these questions we need a calculus of relations suitable for expressing and manipulating specifications of optimisation problems.

3 A Calculus of Relations

This section gives a brief introduction to a calculus of relations designed for the purpose of solving optimisation problems [15]. The exposition makes use of some elementary notions from category theory, namely category, functor, terminal object, product, coproduct, and algebra for an endofunctor. Readers not familiar with this material can find it (for example) in the textbook by Barr and Wells [2]. There are also a number of introductions that focus on applications to program derivation [6, 11, 12, 14, 17]; these are especially suited as background for the present paper.

3.1 Relations

Sets are denoted by upper case identifiers: A, B, C . A relation between A and B is a subset of the cartesian product A × B and we write a(R)b as shorthand for (a, b) ∈ R. The category Rel of sets and relations has sets as objects and relations as arrows. We write R : A ← B for a relation to A from B. The set A is called the target of R and B the source. Composition of relations is defined by

a(R · S)c ≡ (∃b : a(R)b ∧ b(S)c),

and the converse R^{∘} by b(R^{∘})a ≡ a(R)b. A relation R : A ← B is said to be simple if R · R^{∘} ⊆ id_{A}, and entire if id_{B} ⊆ R^{∘} · R. Simple relations are also known as imps, partial functions or partial maps; and entire relations are also called total relations. A relation is a function if it is both entire and simple. Functions will be denoted by lower case identifiers. The two inequations which state that f is a function can also be phrased as an equivalence: f is a function if and only if

(R · f^{∘} ⊆ S) ≡ (R ⊆ S · f )

for all R and S. Equivalently, f is a function if and only if

(f · R ⊆ S) ≡ (R ⊆ f^{∘} · S)

for all R and S. We shall refer to these equivalences as the shunting rules for functions. Sets and functions form a subcategory Fun of Rel.

Intersection and union. Given two relations R, S : A ← B the intersection (R ∩ S) is defined by the equivalence

T ⊆ (R ∩ S) ≡ (T ⊆ R) ∧ (T ⊆ S).

In other words, R ∩ S is the greatest lower bound of R and S. Intersection and converse are related by the so–called modular law,

(R · S) ∩ T ⊆ (R ∩ (T · S^{∘})) · S,

which is also known as Dedekind’s rule. An importance consequence is that composition with simple relations distributes over intersection:

(R ∩ T ) · S = (R · S) ∩ (T · S), provided S is simple.

The inclusion (⊆) is an instance of monotonicity, and the containment (⊇) follows from the modular law and simplicity:

(R · S) ∩ (T · S) ⊆ (R ∩ (T · S · S^{∘})) · S ⊆ (R ∩ T ) · S.

The union R ∪ S of two relations R, S : A ← B is their least upper bound:

R ∪ S ⊆ T ≡ (R ⊆ T ) ∧ (S ⊆ T ).

In contrast to intersection, we have

(R ∪ T ) · S = (R · S) ∪ (T · S)

without any restriction on S.

Knaster-Tarski. For any two sets A and B, the relations A ← B form a complete lattice. We can therefore appeal to the well-known theorem of Knaster and Tarski for solving recursion equations. A modern proof of this theorem can be found in [5].

Theorem 1. Let (L, ≤) be a complete lattice, and let ϕ : L ← L be a monotonic function. Then the equation ϕ x = x has a least solution which is also the least solution of ϕ x ≤ x.

Quotient. Suppose R : A ← B and S : C ← B are relations with a common source. Then the quotient R/S : A ← C is defined by the equivalence

(T ⊆ R/S) ≡ (T · S ⊆ R).

One can also construct R/S explicitly:

c(R/S)b = (∀a : b(S)a ⇒ c(R)a).

Using the characterisation of quotients and the shunting rules for functions, we get

T ⊆ (R/S) · f ≡ T · f^{∘} ⊆ R/S ≡ T · f^{∘} · S ⊆ R ≡ T ⊆ R/(f^{∘} · S).

Hence (R/S) · f = R/(f^{∘} · S). Similar reasoning gives f^{∘} · (R/S) = (f^{∘} · R)/S.

Powersets. The representation of a relation R : A ← B as a subset of the cartesian product A×B is the traditional one, but it is also possible to consider a relation as a set– valued function ΛR : PA ← B, where PA denotes the power set of A. The isomorphism between relations and set–valued functions is described by the equivalence

(f = ΛR) ≡ (∈ · f = R),

where the function ΛR, called the power transpose of R, is defined by

(ΛR) b = {a | a(R)b},

and ∈ : B ← PB is the membership relation. Various useful identities can be derived from the above equivalence. For instance, by taking f = id and R = ∈ in the right-hand side, one finds that

Λ∈ = id.

By taking f = ΛR in the left-hand side, we obtain

∈ · ΛR = R.

3.2 Minimum Elements

For R : A ← A, the relation min(R) : A ← PA is defined by

min(R) = ∈ ∩ (R/∋),

where ∋ denotes the converse of ∈. In words, a(min(R))x if a is an element of x, and for all b, if b ∈ x, then a(R)b. We can define max(R) = min(R^{∘}), so the restriction to minimum elements is not important. We will need various properties of min(R), the first of which is

min(R) · ΛS = S ∩ R/S^{∘}.

Note that this specializes to the definition of min when S = ∈, because Λ∈ = id. This result may be proved as follows

min(R) · ΛS
= {definition of min(R)}
(∈ ∩ R/∋) · ΛS
= {since ΛS is simple}
(∈ · ΛS) ∩ (R/∋) · ΛS
= {since ∈ cancels Λ}
S ∩ (R/∋) · ΛS
= {quotient, ΛS function}
S ∩ R/((ΛS)^{∘} · ∋)
= {converse and ∈ cancels Λ}
S ∩ R/S^{∘}.

A useful fact in applications is the following result which says that we can always constrain min(R) to take account of context.

Proposition 2. If S is simple, then min(R) · S = min(R′) · S, where R′ = (∈ · S) · (∈ · S)^{∘} ∩ R.

Proof. Observe that if S is simple, then (by left-distributivity of (·S) over ∩)

min(R) · S = ∈ · S ∩ (R/∋) · S
min(R′) · S = ∈ · S ∩ ((∈ · S) · (∈ · S)^{∘})/∋ · S ∩ (R/∋) · S

It is therefore sufficient to show that

∈ · S ⊆ ((∈ · S) · (∈ · S)^{∘})/∋ · S.

For any S we have (by the modular law) S ⊆ S · S^{∘} · S, and therefore ∈ · S ⊆ ∈ · S · S^{∘} · S. Since (by the definition of quotients)

∈ · S · S^{∘} ⊆ ((∈ · S) · (∈ · S)^{∘})/∋,

the claim is established.

Corollary 3. We have

min(R) · Λ S^{∘} = min(S^{∘} · S ∩ R) · Λ S^{∘}.

Moreover, S^{∘} · S ∩ R is transitive if R is transitive and S is simple.

Proof. The first part is immediate since Λ S^{∘} is simple and ∈·Λ S^{∘} = S^{∘}. For the second part we argue

(S^{∘} · S ∩ R) · (S^{∘} · S ∩ R)
⊆ {monotonicity}
S^{∘} · S · S^{∘} · S ∩ R · R
⊆ {since S is simple}
S^{∘} · S ∩ R · R
⊆ {since R is transitive}
S^{∘} · S ∩ R.

3.3 Relators

The class of monotonic functors Rel ← Rel plays a fundamental role in the calculus of relations. A functor F : Rel ← Rel is monotonic if R ⊆ S implies FR ⊆ FS. The following theorem states the most important properties of monotonic functors. A detailed proof can be found in the paper by Carboni, Kelly and Wood [4].

Proposition 4. Suppose that F : Rel ← Rel is monotonic. Then

– F preserves functions, i.e. for all f in Fun, Ff is a function.

– F preserves converse, i.e. F(R^{∘}) = (FR)^{∘}.

– F is determined by its action on functions. That is, if G : Rel ← Rel is another monotonic functor, the statement

Ff = Gf for all f in Fun

is equivalent to F = G.

In words, the last property says that each monotonic functor is the unique extension of some functor F : Fun ← Fun to relations. We will use the same letter F to denote both a functor on Fun and its extension to Rel. When a functor on Fun has an extension to relations, it is said to be a relator.

Proposition 5. A functor F : Fun ← Fun is a relator if and only if the following condition is satisfied: f · g^{∘} = h^{∘} · k implies Ff · (Fg)^{∘} = (Fh)^{∘} · Fk.

Most functors that occur in programming problems are relators, and we now consider some examples.

Product. The extension of the product functor × : Fun ← (Fun × Fun) is given by

R × S = (π_{1}^{∘} · R · π_{1}) ∩ (π_{2}^{∘} · S · π_{2})

where π_{1} : A ← A × B and π_{2} : B ← A × B are the left and right projection functions. However, the extended product × does not define a categorical product in Rel, so here the decision to use the same notation for the extension to relations is misleading.

Coproduct. The coproduct functor + : Fun ← (Fun × Fun) also extends to relations; we have

R + S = ι_{1} · R · ι_{1}^{∘} ∪ ι_{2} · S · ι_{2}^{∘},

where ι_{1} : A + B ← A and ι_{2} : A + B ← B are the coproduct injections. Unlike product, + does define a categorical coproduct in Rel, so the use of the same notation is harmless. Since Rel is isomorphic to its own opposite, + also defines a product in Rel.

List. The list functor L : Fun ← Fun takes a set A and returns the set A^{∗} of all finite sequences with elements from A. On arrows, (Lf ) is the function that applies f to all elements of a sequence:

Lf [a_{1}, a_{2}, …, a_{n}] = [f a_{1}, f a_{2}, …, f a_{n}].

The extension of L to relations is defined by

[a_{1}, a_{2}, …, a_{n}](LR)[b_{1}, b_{2}, …, b_{m}] =
(n = m) ∧ (∀i : 1 ≤ i ≤ n : a_{i}(R)b_{i}).

Powerset. Finally, consider the covariant powerset functor P : Fun ← Fun that sends a function to its existential image. Here, PA is the powerset of A and (Pf ) x = {f a | a ∈ x}. The extension of P to relations is defined by

x(PR)y = (∀a ∈ x : ∃b ∈ y : a(R)b) ∧ (∀b ∈ y : ∃a ∈ x : a(R)b).

Note that P : Rel ← Rel is not the same as the existential image functor E : Rel ← Rel defined by EA = PA and

(ER) x = {a | ∃b ∈ x : a(R)b}.

The functor P returns relations and is monotonic, while E returns functions and is not monotonic. Since P and E coincide on functions, we may conclude that the restriction to monotonic functors in proposition 4 is necessary.

Since for every A we have a relation ∈ : A ← PA, one might expect it to be some sort of natural transformation, both with respect to E and P. Indeed, we have

∈ · E R = R · ∈ and ∈ · P R ⊆ R · ∈.

As an application of these facts, we prove a technical proposition that will be useful in later proofs. It states a rule for eliminating min, P and Λ.

Proposition 6.

min(R) · PS · Λ T^{∘} · T ⊆ R · S

Proof. First observe that

Λ T^{∘} · T ⊆ ∋
≡ {Λ T^{∘} function, shunting}
T ⊆ (Λ T^{∘})^{∘} · ∋
≡ {converse}
T ⊆ (∈ · Λ T^{∘})^{∘}
≡ {∈ cancels Λ}
T ⊆ (T^{∘})^{∘}
≡ {converse is an involution}
true.

Using this auxiliary result, we can prove the proposition:

min(R) · PS · Λ T^{∘} · T
⊆ {above}
min(R) · PS · ∋

⊆ {naturality of ∈ (see below)}
min(R) · ∋ · S
⊆ {def. min}
R/∋ · ∋ · S
⊆ {quotient}
R · S.

In the second step, we exploited the naturality of ∈ in the following way:

PS · ∋
= {converse}
(∈ · (PS)^{∘})^{∘}
= {P relator, Prop. 4}
(∈ · P S^{∘})^{∘}
⊆ {naturality of ∈}
(S^{∘} · ∈)^{∘}
= {converse}
∋ · S

This completes the proof.

Once it is known how a functor can be extended from functions to relations, it is easy to extend other operators as well. Consider for instance the split operator ⟨ , ⟩, which is defined on two functions with a common source by the equation

⟨f , g⟩ a = (f a, g a).

For relations R and S we have

⟨R, S⟩ = (R × S) · ⟨id, id⟩.

Such derived operators do not necessarily satisfy the same properties as their functional counterparts. For example, we have that π_{1} · ⟨R, S⟩ ⊆ R but ⊆ cannot be replaced by =.

3.4 Algebras and Catamorphisms

Let F : A ← A be a functor on some category A. By definition, an F–algebra is an arrow f : A ← FA. The object A is said to be the carrier of f .

If f : A ← FA and g : B ← FB are F–algebras, then an F–homomorphism from f to g is an arrow h : A ← B of A such that h · f = g · Fh. The composition of two F–homomorphisms is again an F–homomorphism, so the F–algebras in A form a category in which the objects are F–algebras and the arrows are F–homomorphisms. When this category has an initial object α, and f is another F–algebra, we write ([f ]) to denote the unique F–homomorphism from α to f . Homorphisms of the form ([f ]) are called catamorphisms. Initiality can thus be phrased as the equivalence

(h = ([f ])) ≡ (h · α = f · Fh).

Not all functors Fun ← Fun have an initial algebra, for example, the existential image functor P does not. However, all polynomial functors Fun ← Fun do (see [13]). The class of polynomial functors is inductively defined by the following clauses:

1. The identity functor and constant functors are polynomial;

2. if F and G are polynomial, then so are their composition FG, their sum F + G and their product F × G, where

(F + G) f = Ff + Gf
(F × G) f = Ff × Gf .

All polynomial functors are relators. For any relator F , the initial algebra α of F : Fun ← Fun is also an initial algebra of F : Rel ← Rel. We also have that ([R]) is simple if R is. Proofs of these facts can be found in [1, 15].

In the category of functions, the universal property of the initial algebra α can only be specified as an equation, for equality is the only way of comparing two functions. For relations, the situation is different: here we can also talk in terms of inclusion. The following result, which is an easy consequence of the Knaster–Tarski fixpoint theorem, shows how the universal property of α can be weakened to deal with inclusions.

Proposition 7. For all R and S we have

(R · α = S · FR) ≡ (R = ([S]))
(R · α ⊆ S · FR) ⇒ (R ⊆ ([S]))
(R · α ⊇ S · FR) ⇒ (R ⊇ ([S])).

It is well-known that the initial algebra α is in fact an isomorphism [9], and therefore we have, for instance,

(R = S · FR · α^{∘}) ≡ (R = ([S])).

4 Dynamic Programming

In this section we restate a result of De Moor [15]. Throughout, we assume F is a relator and α is its initial algebra.

We shall need the following definition. A function f : A ← FA is monotonic with respect to a relation R : A ← A if

f · FR ⊆ R · f .

To illustrate this definition, consider numerical addition + : N ← (N × N ), where N is the set of natural numbers. Addition is an algebra of the functor F given by FA = A × A and Ff = f × f . Now, addition is monotonic with respect to ≤. The definition above translates to

(∃a, b : c = a + b ∧ a ≤ a′ ∧ b ≤ b′) ⇒ c ≤ a′ + b′,

and corresponds to the normal definition of monotonicity of + in both arguments.

Theorem 8. (De Moor [15]) Let R be a preorder, and let P be an F-algebra. Define T = min(R) · Λ ([P])^{∘}. If α is monotonic with respect to R, then the least solution D of the equation

D = min(R) · P(α · FD) · Λ P^{∘}

satisfies D ⊆ T .

Before giving the proof of this theorem, let us briefly consider its intuitive interpretation. The recursion equation for D is in line with the operational description of dynamic programming in the introduction to this paper. The function Λ P^{∘} splits the argument in all possible ways. This yields a set of decompositions, and for each of these decompositions, we recursively compute solutions to subproblems. The expression

P(α · FD) · Λ P^{∘}

generates a set of candidate solutions, and min(R) selects a minimum element.

Turning to the proof of the Dynamic Programming Theorem, we note that (by Knaster-Tarski) it suffices to show

min(R) · P(α · FT ) · Λ P^{∘} ⊆ T .

Since T = min(R) · Λ ([P])^{∘} = ([P])^{∘} ∩ R/([P]), this proof obligation can be split into two simpler conjuncts:

min(R) · P(α · FT ) · ΛP^{∘} ⊆ ([P])^{∘}

and

min(R) · P(α · FT ) · ΛP^{∘} · ([P]) ⊆ R.

The first conjunct is proved as follows:

min(R) · P(α · FT ) · ΛP^{∘}
⊆ {def. min}
∈ · P(α · FT ) · ΛP^{∘}
⊆ {naturality of ∈}
α · FT · ∈ · ΛP^{∘}
= {∈ cancels Λ}
α · FT · P^{∘}
= {def. T }
α · F(min(R) · Λ ([P])^{∘}) · P^{∘}

⊆ {def. min}
α · F(∈ · Λ ([P])^{∘}) · P^{∘}
= {∈ cancels Λ}
α · F([P])^{∘} · P^{∘}
= {converse}
(P · F([P]) · α^{∘})^{∘}
= {catamorphism}
([P])^{∘}.

It remains to show that

min(R) · P(α · FT ) · Λ P^{∘} · ([P]) ⊆ R.

This can be done as follows:

min(R) · P(α · FT ) · Λ P^{∘} · ([P])
= {catamorphism}
min(R) · P(α · FT ) · Λ P^{∘} · P · F([P]) · α^{∘}
⊆ {Prop. 6}
R · α · FT · F([P]) · α^{∘}
= {F functor}
min(R) · ∋ · α · F(T · ([P])) · α^{∘}
⊆ {def. T , Prop. 6}
min(R) · ∋ · α · FR · α^{∘}
⊆ {monotonicity}
R · R
⊆ {R transitive}
R.

This completes the proof of the Dynamic Programming Theorem.

Let T = min(R) · Λ ([P])^{∘}, as in the Dynamic Programming Theorem. Using Corollary 3 we have T = min(R′) · Λ ([P])^{∘}, where R′ = ([P])^{∘} · ([P]) ∩ R. Furthermore, R′ is transitive if R is and if P is simple. This means we have only to establish that α is monotonic with respect to R′ in order to apply the dynamic programming theorem. In most practical applications we are not given the relation R but rather a cost function c, i.e. R = c^{∘} · S · c for some preorder S. The proof of the following useful proposition is omitted.

Proposition 9. Suppose R = c^{∘} · S · c, where c satisfies

c · α = k · F⟨([P]), c⟩,

for some k that is monotonic with respect to S, i.e. k · F(id × S) ⊆ S · k. Then, provided P is entire, we have that α is monotonic with respect to ([P])^{∘} · ([P]) ∩ R.

4.1 Application

Let us now apply the above theory to the maximum lateness problem. Let J denote the type of jobs. The type of sequences over J is the initial algebra of the functor F : Fun ← Fun given by

FA = 1 + (A × J )
Fh = id + (h × id),

where 1 denotes the terminal object of Fun. This initial algebra will be denoted by α = [ν, ++<]. Applied to the single element of 1, the function ν returns the empty sequence [ ]. Applied to (x, a) the function ++< returns x ++< a = x ++ [a]. That is, we suppose that sequences are constructed from left to right. There is of course a dual method that constructs sequences from right to left, but the left–to–right bias in the maximum lateness problem means that the given way of constructing sequences is the more appropriate.

Bags of jobs form an F –algebra [ν, +<], where ν returns the empty bag, and x +< a denotes the bag formed by adding a to the bag x. The function bagify = ([ν, +<]) turns a sequence into a bag, and perms = Λ bagify^{∘} returns the set of permutations of a bag.

Recall that the cost function c associated with the lateness problem satisfies

c [ ] = −∞
c(x ++ [a]) = c x ⊔ (bagify x ⊗ a).

Hence

c · α = k · F⟨bagify, c⟩

where k = [−∞, ⊙] and ⊙ is defined by

(x, n) ⊙ a = n ⊔ (x ⊗ a).

In order to make use of Proposition 9 we need to check that

k · F(id × (≤)) ⊆ (≤) · k.

Unfolding the various definitions we get the implication

m ≤ n ⇒ (x, m) ⊙ a ≤ (x, n) ⊙ a.

But this is immediate from the definition of ⊙. The conclusion is that dynamic programming is applicable to the maximum lateness problem.

5 Greedy Algorithms

Now we turn to greedy algorithms. The following theorem is similar to the dynamic programming theorem but involves an extra condition.

Theorem 10. Let T = min(R) · Λ ([P])^{∘}, where R is transitive. Suppose that α is monotonic with respect to R, and β = F([P]) · α^{∘} satisfies S · β ⊆ β · R for some S. Then the (unique) solution G of the equation

G = α · FG · min(S) · Λ P^{∘}

satisfies G ⊆ T .

Proof. Let U = min(S) · Λ P^{∘}. We first show that G = ([U^{∘}])^{∘} is the unique solution of the equation G = α · FG · U .

G = ([U^{∘}])^{∘}
≡ {converse}
G^{∘} = ([U^{∘}])
≡ {Proposition 7}
G^{∘} · α = U^{∘} · FG^{∘}
≡ {converse; F preserves converse}
α^{∘} · G = FG · U
≡ {α is an isomorphism}
G = α · FG · U .

Next, we have

G ⊆ T
⇐ {above form for G and Proposition 7}
α · FT · U ⊆ T
≡ {since T = ([P])^{∘} ∩ R/([P])}
α · FT · U ⊆ ([P])^{∘} and α · FT · U ⊆ R/([P]).

We establish these inclusions separately.

α · FT · U ⊆ ([P])^{∘}
⇐ {since T ⊆ ([P])^{∘} and U ⊆ G^{∘}}
α · F([G])^{∘} · G^{∘} ⊆ ([G])^{∘}
≡ {Proposition 7}
true.

Second, α · FT · U ⊆ R/([P]) is equivalent to α · FT · U · ([P]) ⊆ R. The latter inclusion may be proved as follows:

α · FT · U · ([P])
= {Proposition 7, α isomorphism}
α · FT · U · P · F([P]) · α^{∘}
⊆ {def. U , Prop. 6}
α · FT · S · F([P]) · α^{∘}
⊆ {assumption}
α · FT · F([P]) · α^{∘} · R
= {since F is a functor}
α · F(T · ([P])) · α^{∘} · R
⊆ {def. T , Prop. 6}
α · FR · α^{∘} · R
⊆ {since α is monotonic}
α · α^{∘} · R · R
= {since α is an isomorphism}
R · R
⊆ {R is transitive}
true.

The proof is complete.

The conclusion of the theorem says that there is a greedy algorithm for T . At each step of the computation, one chooses an optimal splitting with min(S) · Λ P^{∘}. Subsequently, the subproblem(s) are solved by means of FG, and the solutions are composed into a solution for the whole problem by α. Note that we can again use Corollary 3 to rewrite U in the form U = min(S′)·Λ P^{∘}, where S′ = P^{∘} ·P ∩S. As in the case of monotonicity, we state a proposition that eases the task of verifying the extra condition in the greedy theorem. Like Proposition 9, its proof is omitted.

Proposition 11. Suppose that F = F_{0} + F_{1}, and α = [α_{0}, α_{1}]. Furthermore, assume that S = S_{0} + S_{1}, and P = [P_{0}, P_{1}], and ([P])^{∘} is entire. Then

(P^{∘} · P ∩ S) · F([P]) · α^{∘} ⊆ F([P]) · α^{∘} · (([P])^{∘} · ([P]) ∩ R)

if and only if

(P_{i}^{∘} · P_{i} ∩ S_{i}) · F_{i}([P]) ⊆ F_{i}([P]) · α_{i}^{∘} · R · α_{i} for i = 0, 1.

5.1 Application

Let us go back to the maximum lateness problem. It has already been shown that α is monotonic, so it remains to verify that with P = [ν, +<], and S′ = P^{∘} · P ∩ S for some suitable S, and R = (bagify^{∘} · bagify) ∩ (c^{∘} · (≤) · c), we have

S′ · Fbagify · [ν, ++<]^{∘} ⊆ Fbagify · [ν, ++<]^{∘} · R.

Choose S = id + ((⊗)^{∘} · (≤) · (⊗)). Proposition 11 says that the proof obligation is equivalent to

(u ⊗ a) ≤ ((bagify y) ⊗ b) ∧ (u +< a) = ((bagify y) +< b)

⇒ ∃x : u = bagify x ∧ c (x ++ [a]) ≤ c (y ++ [b]).

To prove this implication, we consider two cases: a = b and a ≠ b. In the case a = b we have u = bagify y, and so we can take x = y. On the other hand, if a ≠ b, we argue

c(x ++ [a]) ≤ c(y ++ [b])

= {definition of c}

c x ⊔ (u ⊗ a) ≤ c y ⊔ (bagify y ⊗ b)

= {since u ⊗ a ≤ bagify y ⊗ b}

c x ≤ c y ⊔ (bagify y ⊗ b)

= {definition of c}

c x ≤ c (y ++ [b]).

Now, since u +< a = (bagify y) +< b and a ≠ b, there exist y_{0} and y_{1} such that y = y_{0} ++ [a] ++ y_{1}. Take x = y_{0} ++ y_{1} ++ [b]. We claim that c x ≤ c (y ++ [b]). More generally, we have c (w ++ z) ≤ c (w ++ [a] ++ z) for all w, z, and a. This follows by induction on z, using the result

(w ++ z) ⊗ b
= {definition of ⊗}
wt b × ((∑_{c∈w+ +z} time c) + time b − due b)
≤ {since weights and times are nonnegative}
wt b × ((∑_{c∈w+ +[a]+ +z} time c) + time b − due b)
= {definition of ⊗}
(w ++ [a] ++ z) ⊗ b.

The conclusion is that the maximum lateness problem can be computed by a greedy algorithm.

6 Conclusions

One of the aims of the paper was to clarify the relationship between dynamic programming and certain greedy algorithms. This relationship is captured in the very similar statements of the dynamic programming and greedy theorems.

It is important to note that the greedy theorem gives general conditions under which a greedy solution is possible, but does not discuss mathematical systems in which the greedy condition is valid. Two such systems are known: those of a matroid and those of a greedoid (see [8]). Essentially, the verification of the greedy condition for the maximum lateness problem is an application of greedoid theory. It remains to be seen whether our approach gives further insight into such systems.

Finally, because the greedy theorem holds for tree algebras and not just lists, it may also have applications in the derivation of divide–and–conquer algorithms. Here a comparison with Smith’s approach to divide–and–conquer [16] could be a fruitful research topic.

References

1. R.C. Backhouse, P. Hoogendijk, E. Voermans, and J.C.S.P. van der Woude. A relational theory of datatypes. Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands., June 1992.

2. M. Barr and C. Wells. Category Theory for Computing Science. Prentice–Hall, 1990.

3. R.S. Bird and O. de Moor. List partitions. Formal Aspects of Computing, 5(1):61–78, 1993.

4. A. Carboni, G.M. Kelly, and R.J. Wood. A 2–categorical approach to geometric morphisms, i. Cahiers de Topologie et Geometrie Differentielle Categoriques, 32(1):47–95, 1991.

5. E.W. Dijkstra. A Discipline of Programming. Prentice–Hall, 1976.

6. Maarten M. Fokkinga. Law and Order in Algorithmics. PhD thesis, Technical University Twente, The Netherlands, 1992.

7. D.S. Hochbaum and R. Shamir. An O(n log^{2} n) algorithm for the maximum weighted tardiness problem. Information Processing Letters, 31:215–219, 1989.

8. B. Korte, L. Lovasz, and R. Schrader. Greedoids, volume 4 of Algorithms and combinatorics. Springer–Verlag, 1991.

9. J. Lambek. A fixpoint theorem for complete categories. Mathematische Zeitschrift, 103:151–161, 1968.

10. E.L. Lawler. Optimal sequencing of a single machine subject to precedence constraints. Management Science, 19(5):544–546, January 1973.

11. G. Malcolm. Homomorphisms and promotability. In J. L. A. van de Snepscheut, editor, Mathematics of Program Construction, volume 375 of Lecture Notes in Computer Science, pages 335–347. Springer–Verlag, 1989.

12. G. Malcolm. Data structures and program transformation. Science of Computer Programming, 14:255–279, 1990.

13. E.G. Manes and M.A. Arbib. Algebraic Approaches to Program Semantics. Texts and Monographs in Computer Science. Springer–Verlag, 1986.

14. L. Meertens. Paramorphisms. Formal Aspects of Computing, 4(5):413–424, 1992.

15. O. de Moor. Categories, relations and dynamic programming. D.Phil. thesis. Technical Monograph PRG-98, Computing Laboratory, Oxford, 1992.

16. D.R. Smith. Applications of a strategy for designing divide–and–conquer algorithms. Science of Computer Programming, 18:213–229, 1987.

17. M. Spivey. A categorical approach to the theory of lists. In J. L. A. van de Snepscheut, editor, Mathematics of Program Construction, volume 375 of Lecture Notes in Computer Science, pages 399–408. Springer–Verlag, 1989.

This article was processed using the LaTEX macro package with LMAMULT style