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.Interval Scheduling and Bipartite Matching are special cases of the Independent Set Problem.

For Interval Scheduling, if you define a graph G = (V,E) in which nodes are the intervals and there is an edge between each pair of them that overlap, then the independent sets in G are just the compatible subsets of intervals. For the Bipartite Matching, given a bipartite graph G' = (V',E'), the objects being chosen are edges, and the conflicts arise between two edges that share an end.Let us define a graph G = (V,E) in which the node set V equals to the edge set E' of G'. We define an edge between each pair of elements in V that correspond to edges of G' with a common end. All that is left is to check that the independent sets of G' are precisely the matchings of G'.

Today, an efficient algorithm to solve this problem is not known and it is conjectured that no efficient algorithm exists. The best that can be done to this day is to use brute-force to try all subsets of the nodes,checking each to see if it is independent, and then recording the largest one encountered. The Independent Set Problem is one of a large class of problems called NP-complete.

Lets' consider two large companies P1 and P2,currently competing for market share in a geographic area. P1 opens a franchise,then P2 opens a franchise,then P1 and so on. Suppose zoning regulations require that no two franchises can be located too close together and each company is trying to make its location as convenient as possible. The problem is : who will win?

Formulating the problem:

• the geographic region in question is divided into n zones,labeled 1,2,…,n.
• Each zone i has a value b_i which is the revenue obtained by either of the companies if it opens a franchise there.
• Certain zones (i,j) are adjacent, and local zoning laws prevent two adjacent zones from each containing a franchise regardless of which company owns them. They also prevent two franchises from being opened in the same zone.
• We model those conflicts using a graph G = (V,E) where V is the set of zones, and (i,j) is an edge in E if the zones i and j are adjacent
• The zoning requirement then says the full set of franchises opened must form an independent set in G.
• Thus our problem consists of the two players, P1 and P2, alternatively selecting nodes in G,with P1 moving first.At all times, the set of all selected nodes must form an independent set in G.
• Suppose that player P2 has a target bound B and we want to know if there is a strategy for P2 such that no matter how P1 plays,P2 will be able to select a set of nodes with a total value of at least B. This is an instance of the Competitive Facility Location Problem.

Not only is it computationally difficult to determine whether a player has a winning strategy, on a reasonably sized graph, it would be hard to be convinced that a player has a winning strategy. The Competitive Facility Location Problem belongs to the class of PSPACE-complete problems. This class of problems is much harder than the class of NP-complete problems.

Motivations for discussing the five representative problems is obvious: They will serve as reference as we solve problems relating to algorithms. They simply form a reference for other problems. The question I have though is: “Do these problems represent all of the problems we can ever encounter when dealing with algorithm analysis or they serve as reference for most of the problems?”. As for proofs, they make sense after carefully reading them. After rereading this section, I was able to see how these problems do arise in real life and how they can cover a wide range of problems.

I want to remember the difference between NP-complete and PSPACE-complete problems: For NP-complete,you can easily check the solutions whilst for PSPACE-complete even checking the solutions is challenging. This is a very important difference that will help me identify the hard problems I will be presented with.

Since this section was straightforward,essential and very interesting,I give this reading a 9/10.