Differences

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

--- courses:cs211:winter2012:journals:ian:chapter1 [2012/01/18 03:57] – [1.2: Five Representative Problems] sturdyi
+++ courses:cs211:winter2012:journals:ian:chapter1 [2012/01/18 03:57] (current) – [1.2: Five Representative Problems] sturdyi
@@ Line 10: / Line 10: @@
    * Some problems are readily solved, albeit potentially requiring a quite subtle algorithm; others resist efficient analysis unless somehow qualified. Interval scheduling is readily solved by a one-pass greedy algorithm, while weighted interval scheduling requires a more sophisticated approach except in degenerate special cases. Bipartite matching is a superset of the stable matching problem, but still admits an efficient solution to the general case. Independent set finding is an even broader problems, encompassing both interval scheduling and bipartite matching (and thus stable matching) as special cases; however, no solution is known for this general case, and it is NP-complete, so that the existence of such an algorithm is doubtful. Lastly, the competitive facility location problem is yet harder, with no known algorithm much better than brute force.
-    * No insights.
+   * No insights.
-    * No questions.
+   * No questions.
-    * I would have liked to see an explication of greedy algorithms and, in particular, the algorithm to solve interval scheduling; looking it up on my own neither seemed too burdensome. 7/10.
+   * I would have liked to see an explication of greedy algorithms and, in particular, the algorithm to solve interval scheduling; looking it up on my own neither seemed too burdensome. 7/10.