1.2 Five Representative Problems

The five representative problems are cleanly formulated problems encountered very often in the study of algorithms,all resembling one another at a general level but differing greatly in their difficulty and in the kinds of approaches taken to solve them. They are all motivated by computing applications. To talk about these problems,the terminology of graphs is used. A graph G consists of a pair of sets (V,E)-a collection of V nodes and a collection of E edges, each of which joins two of the nodes.Thus an edge e in E is a two-element subset of V : e = {u,v}.

The five representative problems are:

• Interval Scheduling
  

This problem arise when there is a situation where one has a resource and many people request to use the resource for periods of time. A request is like this: Can I reserve the resource starting at time s,until time f?. The assumption is that the resource can be used by at most one person at a time. A scheduler accepts a subset of the requests, rejecting others, so that the accepted requests do not overlap in time.The goal is to maximize the number of requests accepted. There will be n requests labeled 1,…,n, with each request i specifying a start time s_i and a finish time f_i.

Two requests are compatible if the requested intervals do not overlap. A subset A of requests is compatible if all pairs of requests i,j in A, i different from j, are compatible. The goal is to select a compatible subset of requests of maximum possible size.

This problem can be solved by an algorithm that orders the set of requests according to a certain heuristic and then “greedily” processes them in one pass,selecting as large a compatible subset as it can. This will be a class of greedy algorithms:myopic rules that process the input one piece at a time with no apparent look-ahead.

• Weighted Interval Scheduling
  

In this situation, each request interval i has an associated value,or weight, v_i > 0.The goal is to find a compatible subset of intervals of maximum total value. The case in which v_i = 1 is the basic Interval Scheduling Problem. Any algorithm for this problem must be very sensitive to the values, and yet degenerate to a method for solving(unweighted) Interval Scheduling when all values equal 1.

To solve this problem, a technique called dynamic programming that builds up the optimal value over all possible solutions in a compact,tabular way is employed.

• Bipartite matching