greedy-exchange.md

Motivation

In my Algorithms class, the unit on greedy algorithms was relatively challenging. The idea of an "exchange argument" is conceptually complicated, and I found that the explanations given in class and online were always encumbered by the details of the specific problem being solved. I am writing this gist so that there is something on the internet that will aid other undergraduates taking this course. My goal is to be both succinct and abstract. This will show both of how to a) systematically derive a greedy solution for any problem, and b) use this solution to prove the optimality of the algorithm using an exchange argument.

Instructions

Counterintuitively, we will start by structuring our proof and then derive our algorithm from this structure. In our proof, we will define two objects:

• O, an arbitrary optimal ordering of our set of inputs I
• partialCost(a,b), a function representing the cost of choosing a immediately before b (you should find an equation for this, in stricter terms this is equivalent to the total cost of a solution consisting of two elements a and b, in that order)

The way an exchange argument works is by showing two things:

1. An operation exists that can swap any two values in O by our greedy principle without making it less/unoptimal.
2. This operation can be applied a finite number of times to O to make it identical to the output of our greedy algorithm.

• This is sufficient to prove that our algorithm is optimal, because if our algorithm was not optimal, 1. must have been violated for two values in O.
• To make our argument (and your math) simpler, we will consider the fact that any two elements in a list can be swapped through a series of swaps of sequential elements. To intuitively convince yourself of this, think of bubblesort.
• The operation referred to in 1. will be an equation that orders two elements (we will refer to them as O[i] and O[j]) based on a "greedy" principle:

if(partialCost(O[i],O[j])-partialCost(O[j],O[i])>0) # this difference is the relative cost of choosing ordering O[i],O[j] over O[j],O[i]
  swap(O[i],O[j])  # put O[j] before O[i] if choosing O[i] first would have a higher cost

• We have just proved 1. by instantiation, and 2. is true if our swap operation coincides with our greedy choice. Thus, our exchange argument is complete, and if you have a definition for partialCost, then so is your homework. (your algorithm is to sort I by a binary relation f(a,b)=partialCost(a,b)<partialCost(b,a) using any algorithm of your choice)

The only remote difficulty in this sort of problem arises from having to express your algorithm in a sequence of choices, rather than sorting by an inequality (if your homework requires this). In this case, the solution can be found by solving the inequality partialCost(O[i],O[j])<partialCost(O[j],O[i]) and having all terms related to each of O[i] and O[j] on different sides of the equation. Each side of the equation will be an equation f(I[i]) I -> Reals, which will allow you to assess the cost of choosing a single element on its own, and thus make a single greedy choice from a set of elements without sorting them.