Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| courses:cs211:winter2012:journals:ian:chapter1 [2012/01/17 22:20] – created sturdyi | courses:cs211:winter2012:journals:ian:chapter1 [2012/01/18 03:57] (current) – [1.2: Five Representative Problems] sturdyi | ||
|---|---|---|---|
| Line 7: | Line 7: | ||
| * I find all this talk about fairness rather annoying--it may be a curiosity of the algorithm, but is never treated rigorously. Indeed, it is not even a proper part of the problem--the task is to find a stable matching, not a stable //and fair// algorithm. Especially given that this is the first formal example, this seems a most distracting addition. While the discussion of fairness seems to be leading into the proof that the algorithm specifies a single matching for every set of preferences, | * I find all this talk about fairness rather annoying--it may be a curiosity of the algorithm, but is never treated rigorously. Indeed, it is not even a proper part of the problem--the task is to find a stable matching, not a stable //and fair// algorithm. Especially given that this is the first formal example, this seems a most distracting addition. While the discussion of fairness seems to be leading into the proof that the algorithm specifies a single matching for every set of preferences, | ||
| + | ===== 1.2: Five Representative Problems ===== | ||
| + | |||
| + | * 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, | ||
| + | * No insights. | ||
| + | * 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. | ||
