Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:jeanpaul:section2 [2012/01/15 00:01] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:section2 [2012/01/17 05:02] (current) – mugabej
@@ Line 43: / Line 43: @@
 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.
+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//.
+=== Competitive Facility Location===
+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<sub>i</sub>// 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.