Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
courses:cs211:winter2012:journals:ian:chapter1 [2012/01/18 03:57] – Added 1.2 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, | * 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 insights. |
- | | + | |
- | | + | |