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:

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.

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.

A graph G = (V,E) is bipartite if its node set V can be partitioned into sets X and Y in such a way that every edge has one end in X and the other in Y.

• A matching in a graph G = (V,E)is a set of edges M (M included in E) with the property that each node appears in at most one edge of M.
• M is a perfect matching if every node appears in exactly one edge of M
• If we consider a bipartite graph G' with a set X of n men, a set Y of n women, and an edge from every node in X to every node in Y, then the matchings and perfect matchings in G' are exactly the matchings and perfect matchings among the set of men and women. But there are no preference lists in the bipartite graphs problem. The complexity added is that there is not necessarily an edge from every x in X to every y in Y.
  

Matchings in bipartite graphs model situations in which objects are being assigned to other objects. Let the nodes in X represent jobs,the nodes in Y represent machines, and an edge (x_i,y_j) indicate that machine y_j is capable of processing job x_i. A perfect matching is then a way of assigning each job to a machine that can process it, with the property that each machine is assigned exactly one job.

The Bipartite Matching Problem is: Given an arbitrary bipartite graph G,find a matching of maximum size. If |X| = |Y| = n, then there is a perfect matching if and only if the maximum matching has size n.

A technique called augmentation is used to solve this problem: it consists of inductively building up larger and larger matchings, selectively backtracking along the way. This technique forms the central component in a large class of network flow problems.

Given a graph G = (V,E), a set of nodes S (S included in V) is independent if no two nodes in S are joined by an edge.

The Independent Set Problem is the following: Given G, find an independent set that is as large as possible.
This Problem models any situation in which one is trying to choose among a collection of objects and there are pairwise conflicts among some of the objects.