I just finished working on another implementation of Kruskal’s algorithm. This version depends more on user input to generate the minimum spanning path tree.

# Tag Archives: greedy

# Interactive Tutorial of Prim’s Algorithm

I just finished working on another implementation of Prim’s algorithm. This version depends more on user input to generate the minimum spanning path tree.

# Approximating the Set Cover Problem

I just finished my weekly task of shopping for groceries. This can be a somewhat daunting task because I generally have a list of things that I’ll need which cannot all be purchased at a single location. What often happens is that I find that many of the items on my list are ONLY offered at certain stores – generic brands of certain items for example. My goal then changes from minimizing the total amount of money spent to minimizing the number of stores that I must visit to purchase all of my items.

To formulate this as a mathematical problem, suppose that I have a grocery list of items I would like to buy, represented by the lists item_{1}, item_{2}, …, item_{n}, where n represents the number of items I have on this list. Suppose also that there are stores Store_{1}, Store_{2}, …, Store_{m} (each one distinct) that offer some combination of items I have on my list. What I would like to do is minimize the number of stores I have to visit to purchase these items.

The problem I just described is famous because it is one that many people face on a regular basis. In a more general form, it is so famous that it has a name for it, called the Set Cover Problem (or the Minimum Set Cover Problem). In the general form of this problem, we replace the grocery list with a set of items called our universe. The lists of items offered at each store are the collections of subsets of the universe. In the problem, as in the example above, we would like to select enough subsets from this collection that we are able to obtain every element in our universe. We would like to do this with as low a number of sets as possible.

In my previous post, I described the 21 problems that Karp proved were NP-Complete. Set Cover was one of those problems, showing that this is a hard problem to solve. What I will do is introduce three ways to reach a near-optimal solution relatively quickly.

**Greedy Method**

One of the first approaches one may take to solve this problem is to repeatedly select the subset that contains the most new items. That’s how the greedy approach to set cover operates. The method knows to terminate when all elements belong to one of the selected sets. In the shopping example above, this would be accomplished by visiting the store that had the most items on my list and purchasing those items at this store. Once this is done, the items that have been purchased can be crossed off my list and we can visit the store with the most items on my remaining list, stopping when the list is empty.

**Linear Programming Relaxation**

Instead of stating the set cover problem with words, there is a way of describing the situation with mathematical inequalities. For instance, suppose that the soap I like to purchase is only available at stores Store_{1}, Store_{4} and Store_{9}. Then I could introduce a variable x_{i} for each store i and the requirement that I purchase this soap can be restated as :

_{1}+ x

_{4}+ x

_{9}1

Because we can either purchase some items or not purchase these items, each variable x_{i} is 0 or 1 (called a binary variable). We can introduce similar constraints for each element in our universe (or on our grocery list). These inequalities (called constraints) have the form:

for each element e U, _{i | e Si} x_{i} 1

Our goal of minimizing the number of sets chosen (stores visited) can be stated by the objective function:

minimize _{1 i n} x_{i}

So the mathematical formulation for this problem can be stated as

minimize _{1 i n} x_{i}

Subject to

for each element e U, _{i | e Si} x_{i} 1

for each set i, x_{i} {0, 1}.

Formulations of this type, where variables are restricted to a finite set (in this case the x variables being either 0 or 1) are called integer programs. Unfortunately, there is no easy way to solve these formulations either. However, there is a related problem which can be solved quickly.

Instead of restricting the x variables to the values of 0 or 1, we could allow them to take on any value within this range, i.e. 0 x_{i} 1 for each set S_{i}. Doing this converts the problem from an integer programming problem into a linear programming problem (called the LP-Relaxation), which can be solved quickly. The issue with this method though is that the solution obtained by an LP-Relaxation is not guaranteed to be an integer. In this case, how do we interpret the values x_{i}?

**Randomized Rounding Method**

One approach to dealing with a non-integer solution to the LP-Relaxation is to treat the x_{i} values as probabilities. We can say that x_{i} is the probability that we select set i. This works because each value of x_{i} is in the range of 0 to 1, which is necessary for a probability. We need to repeatedly select sets with their associated probabilities until all elements in our universe are covered. Selecting our sets based on this procedure is the randomized rounding approach.

**Deterministic Rounding Method**

A second approach to dealing with a non-integer solution to the LP-Relaxation is to base our solution on the most occurring element. If we let f be this frequency (i.e.the number of sets that the most occurring element occurs in), then we can define a solution by selecting set i if the LP=Relaxation solution gives the variable x_{i} a value of at least (1/f).

None of these three approaches is guaranteed to give an optimal solution to an instance of this problem. I will not go into it in this post, but these can all be shown to be within some guaranteed range of the optimal solution, thus making them approximation algorithms.

You can see how the three algorithms compare on random problem instances here.

Hope you enjoy.

# Knapsack Problems

To help understand this problem, I want you to think about a common situation in many people’s lives. You have a road trip coming up today and you’ve overslept and are at risk of missing your flight. And to top matters off, you were planning to pack this morning but now do not have the time. You quickly get up and begin to get ready. You grab the first bag you see and quickly try to make decisions on which items to take. In your head you’re trying to perform calculations on things you’ll need for the trip versus things that you can purchase when you get there; things that you need to be able to have a good time versus things you can do without. And to top matters off, you don’t have time to look for your ideal luggage to pack these things. So you have the additional constraint that the items you pick must all fit into this first bag you found this morning.

The situation I described above is a common problem. Even if we ignore the part about the flight, and just concentrate on the problem of trying to put the most valuable set of items in our bag, where each item has its own value and its own size limitations, this is a problem that comes up quite often. The problem is known (in the math, computer science and operations research communities) as the knapsack problem. It is known to be difficult to solve (it is said to be NP-Hard and belongs to a set of problems that are thought to be the most difficult problems within its class). Because of this difficulty, this problem has been well studied.

What I provide in my script are two approaches to solving this problem. The first is a greedy approach, which selects a set of items by iteratively choosing the item with the highest remaining value to size ratio. This approach solves very fast, but can be shown to give sub-optimal solutions.

The second approach is a dynamic programming approach. This algorithm will solves the problem by ordering the items 0, 1, …, n and understanding that in order to have the optimal solution on the first *i* items, the optimal solution must have been first selected on the fist *i-1* items. This algorithm will optimally solve the problem, but it requires the computation of many sub-problems which causes it to run slowly.

Update (4/2/2013): I enjoy this problem so much that I decided to implement two additional approaches to the problem: Linear Programming and Backtracking.

The Linear Programming approach to this problem comes from the understanding that the knapsack problem (as well as any other NP-Complete problem) can be formulated as an Integer Program (this is a mathematical formulation where we seek to maximize a linear objective function subject to a set of linear inequality constraints with the condition that the variables take on integer values). In the instance of the knapsack problem we would introduce a variable x_{i} for each item i; the objective function would be to maximize the total value of items selected. This can be expressed as a linear objective function by taking the sum of the products of the values of each item v_{i} and the variable x_{i}; the only constraint would be the constraint saying that all items fit into the knapsack. This can be expressed as a linear inequality constraint by taking the sum of the products of the weights of each item w_{i} and the variable x_{i}. This sum can be at most the total size of the knapsack. In the integer programming formulation, we either select an item or we do not. This is represented in our formulation by allowing the variable x_{i} = 1 if the item is selected, 0 otherwise.

The LP relaxation of an integer program can be found by dropping the requirements that the variables be integer and replacing them with linear equations. So in the case of the knapsack problem, instead of allowing the variables to only take on values of 0 and 1, we would allow the variables to take on any value in the range of 0 and 1, i.e 0 <= x_{i} <= 1 for each item i. We can then solve this LP to optimality to get a feasible solution to the knapsack problem.The second knapsack approach I implemented today is through backtracking. Similar to the Dynamic Programming approach to this problem, the backtracking approach will find an optimal solution to the problem, but these solutions generally take a long time to compute and are considered computationally inefficient. The algorithm I implemented here first orders the item by their index, then considers the following sub-problems for each item i "What is the best solution I can obtain with this initial solution?". To answer this question, the algorithm begins with an initial solution (initially, the empty set) and a set of unchecked items (initially, all items) and recursively calls itself on sub-problems with an additional item as a part of the initial solution and with this item removed from the unchecked items.So check out my knapsack problem page. I think its a good way to be introduced to the problem itself, as well as some of the techniques that are used in the fields of mathematics, computer science, engineering and operations research.

Other Blogs covering this topic:

Journey to the Four Point Oh

# Dijkstra’s Algorithm

I’ve just written a script that executes Dijkstra’s algorithm that seeks to find the shortest path tree on a randomly generated graph.

Given a weighted graph *G* and a vertex *s*, the single node shortest path problem seeks to find the shortest path from *s* to every other vertex in this graph such that the sum of the weights of the edges along these paths is minimized. One famous algorithm for this problem is Dijkstra’s Algorithm, which constructs this shortest path tree using techniques of greedy algorithms and dynamic programming.

Dijkstra’s Algorithm works as follows.

- Initially we have an empty path tree
*T*, and assume that the distance to every vertex in the graph has some maximum cost, say infinity, i.e.*w*(*v*) = infinity for all*v*in*V*. - Add the node
*s*to the tree, and give the associated path cost a value of zero, i.e.*w*(*s*) = 0. - Find the edge which is adjacent to
*T*that adds the vertex whose cost is minimum, i.e. we look for an*e*= (*u*,*v*) such that*u*is in*T*, and*v*is not in*T*and*w*(*u*) + cost(*u*,*v*) <*w*(*v*) is minimum. If no such edge exists go to 5. - Add the corresponding edge and vertex to the tree, and update the weight vector of the vertex
*v*. Go to 3. - The path tree
*T*now represents the shortest path from the vertex*s*to all other vertices reachable in the graph*G*. The weight vector*w*represents the costs of these paths.

For an example of Dijkstra’s algorithm executed on the Graph with the following adjacency matrix:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |

0 | – | – | 2 | 4 | – | – | 20 | – |

1 | – | – | – | 11 | 11 | 7 | 5 | – |

2 | 2 | – | – | – | 10 | – | 7 | – |

3 | 4 | 11 | – | – | – | – | – | 2 |

4 | – | 11 | 10 | – | – | – | – | – |

5 | – | 7 | – | – | – | – | – | 14 |

6 | 20 | 5 | 7 | – | – | – | – | – |

7 | – | – | – | 2 | – | 14 | – | – |

Suppose we are interested in discovering the shortest paths from the node 0.

Initially Dijkstra’s algorithm constructs an empty path tree, T = {}.

Because we want to discover the shortest paths from the node 0, our first step will be to add this node to the tree and update the weight vector.

T = {0}

w(0) = 0.

Now we will consider the edges adjacent to T, {(0, 2), (0, 3), and (0, 6)}. Our assumption is that the shortest path of every vertex in T has already been computed correctly and we will seek the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T. The edge that does that currently is (0, 2) since w(0) = 0 and c(0, 2) = 2. We add the node 2 to T and update the weight vector.

T = {0, 2}

w(2) = 2.

The edges adjacent to T are now {(0, 3), (0, 6), (2, 4), (2, 6)}.

The associated path costs are:

w(0) + c(0, 3) = 0 + 4 = 4

w(0) + c(0, 6) = 0 + 20 = 20

w(2) + c(2, 4) = 2 + 10 = 12

w(2) + c(2, 6) = 2 + 7 = 9

We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (0, 3). We add the node 3 to T and update the weight vector.

T = {0, 2, 3}

w(3) = 4

The edges adjacent to T are now {(0, 6), (2, 4), (2, 6), (3, 1), (3, 7)}.

The associated path costs are:

w(0) + c(0, 6) = 0 + 20 = 20

w(2) + c(2, 4) = 2 + 10 = 12

w(2) + c(2, 6) = 2 + 7 = 9

w(3) + c(3, 1) = 4 + 11 = 15

w(3) + c(3, 7) = 4 + 2 = 6

We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (3, 7). We add the node 7 to T and update the weight vector.

T = {0, 2, 3, 7}

w(7) = 6

The edges adjacent to T are now {(0, 6), (2, 4), (2, 6), (3, 1), (5, 7)}.

The associated path costs are:

w(0) + c(0, 6) = 0 + 20 = 20

w(2) + c(2, 4) = 2 + 10 = 12

w(2) + c(2, 6) = 2 + 7 = 9

w(3) + c(3, 1) = 4 + 11 = 15

w(7) + c(5, 7) = 6 + 14 = 20

We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (2, 6). We add the node 6 to T and update the weight vector.

T = {0, 2, 3, 6, 7}

w(6) = 9

The edges adjacent to T are now {(2, 4), (3, 1), (5, 7) (6, 1)}.

The associated path costs are:

w(2) + c(2, 4) = 2 + 10 = 12

w(3) + c(3, 1) = 4 + 11 = 15

w(7) + c(5, 7) = 6 + 14 = 20

w(6) + c(6, 1) = 9 + 5 = 14

We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (2, 4). We add the node 4 to T and update the weight vector.

T = {0, 2, 3, 4, 6, 7}

w(4) = 12

The edges adjacent to T are now {(3, 1), (5, 7), (6, 1), (4, 1)}.

The associated path costs are:

w(3) + c(3, 1) = 4 + 11 = 15

w(7) + c(5, 7) = 6 + 14 = 20

w(6) + c(6, 1) = 9 + 5 = 14

w(4) + c(4, 1) = 12 + 11 = 23

We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (6, 1). We add the node 1 to T and update the weight vector.

T = {0, 1, 2, 3, 4, 6, 7}

w(1) = 14

The edges adjacent to T are now {(5, 7), (1, 5)}.

The associated path costs are:

w(7) + c(5, 7) = 6 + 14 = 20

w(1) + c(1, 5) = 14 + 7 = 21

We can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (5, 7). We add the node 5 to T and update the weight vector.

T = {0, 1, 2, 3, 4, 5, 6, 7}

w(5) = 20

Now that T contains all the nodes from the tree, we know the shortest path from node 0 to all other nodes and and have solved the problem. The associated weight vector is w = [0, 14, 2, 4, 12, 20, 9, 6].

To learn more and see more examples, view Dijkstra’s Algorithm at LEARNINGlover.com