1. Optimisation Algorithms
Optimisation algorithms seek the best feasible solution under a cost metric and a set of constraints. Unlike path-finding or search problems, the solution need not be a path — it may be a subset selection, assignment, schedule, or flow.
1.1 Algorithms
| Algorithm | Problem | Paradigm | Complexity |
|---|---|---|---|
| Interval Scheduling | Maximise non-overlapping intervals | Greedy | \(O(n \log n)\) |
| 0/1 Knapsack | Maximise value subject to weight capacity | Dynamic programming | \(O(nW)\) |
1.2 Decision vs. Optimisation
Most optimisation problems have a corresponding decision version (does a solution of cost \(\leq k\) exist?). NP-hardness is defined for decision problems, so to show an optimisation problem is NP-hard one reduces its decision version from a known NP-hard problem. When the decision version is polynomial, the optimisation version is polynomial too (e.g. interval scheduling); when the decision version is NP-hard, the optimisation version is NP-hard as well (e.g. 0/1 knapsack).