Differences

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

--- courses:cs211:winter2011:journals:charles:chapter1 [2011/01/27 07:03] – gouldc
+++ courses:cs211:winter2011:journals:charles:chapter1 [2011/01/27 07:07] (current) – gouldc
@@ Line 7: / Line 7: @@
 ===== 1.2 Five Representative Problems =====
-(1)  - Ordered List Item Interval scheduling
+  - Interval scheduling
+  - Weighted interval scheduling
+  - Bipartite matching
+  - Independent set
+  - Competitive facility location
+=== Interval scheduling ===
 And then ITS decreed, "Computer labs shall remain locked at all times and under any circumstances, except when a university professor schedules hours in them in advance." Professor Sprenkle has to register lab times with Steve now. She tells Steve, "I want to use the computer lab on M,W,F from 10:10 am  to 11:05 am." Then Professor Stough enters, asking if he can reserve the room for F, 10:45 to 12:45 to teach a C++ workshop to his CS340 students. How does Steve determine who gets to reserve the room on F morning (there is an overlap from 10:45 to 11:05)? The time overlap of these "requests" makes the requests incompatible, and so one of the requests must be rejected. We want "to select a compatible subset of requests of maximum possible size."
-(2) Weighted interval scheduling
+=== Weighted interval scheduling ===
 This is similar to the interval scheduling problem; the difference is that each request has an associated value (weight). We no longer want to accept the maximum number of compatible requests. We want to accept the subset of requests that yields the maximum sum value.
-(3) Bipartite matching
+=== Bipartite matching ===
 Bipartite graphs can model assignments (likes jobs being assigned to machines). Each job should be matched to a machine, and each machine should be matched to a job. We represent bipartite graphs as two columns of nodes, with edges (assignments) from nodes in the first column to nodes in the second column. The stable matching problem is an example of bipartite matching. More formally, such a problem is defined in the following way: "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."
-(4) Independent set
+=== Independent set ===
 A set of nodes is independent if no two nodes in S are joined by an edge. Example problem: you have n friends, some pairs don't get along. Find the maximum number of friends you can invite to say a birthday party and avoid any conflicts. Interval scheduling and bipartite matching can both be thought of (encoded) as special cases of the independent set problem. There is no efficient algorithm for the independent set problem currently. We will see later that "Independent Set" is one problem in the large class of NP-complete problems.
-(5) Competitive facility location
+=== Competitive facility location ===
 Walmart vs K-Mart. Both companies want to build stores in convenient locations (to increase market share, etc.). But all around the country, local zoning regulations prevent the franchises from being located too near one another. Assume the geographic region over which they are vying for control is divided into n zones (1, 2, ..., n), and each zone has an associated value (the expected revenue for each company if it opens a store there). Who will win the game? Which company will open a store in location X, Y, Z?