Choosing the Right Paradigm for Optimization Problems
What This Concept Is
Algorithm selection is a reasoned decision under an explicit problem contract: input domain and limits, feasible objects, objective, exactness requirement, witness format and resource budget. Brute force, greedy, DP and graph algorithms overlap as tools; they are not a sequence in which one is always superior.
Begin with a correct model and a tiny exhaustive solver when feasible. Derive structure, then estimate the resulting state/transition costs. A named pattern does not substitute for proving that its assumptions match the instance.
Why It Matters Here
An exact implementation can be unusable because its table is too large, while a fast heuristic can fail the required exactness guarantee. Resource and output requirements are part of engineering correctness. There is no need to pretend every problem in a DP module must use DP.
Concrete Examples
| Problem contract | Candidate and justification | Boundary that changes the choice |
|---|---|---|
| Maximum number of compatible intervals | Earliest-finish greedy with exchange proof | Job values change cardinality to weighted profit |
| Weighted compatible intervals | Prefix DP with predecessor search | A budget adds a state coordinate |
| Unit-cost edit distance with alignment | Prefix table plus reconstruction | Large string product can exceed memory/time |
| Source path in a DAG with signed edges | Topological DP | Cycles invalidate the one-pass order |
| Hamiltonian tour on a tiny directed graph | Subset DP or permutation oracle | Exponential state growth limits scale |
| Capacity-limited 0/1 choices | Item/capacity DP | Huge numeric capacity makes pseudo-polynomial work costly |
Weighted scheduling with budget. Add positive job costs and budget B.
State D(i,b) is maximum profit from the first i finish-sorted jobs with
total cost at most b. A take transition reads D(p(i-1),b-cost[i-1]).
The old D(i) state loses the remaining budget and is insufficient. Time is
O(n log(n+1)+n(B+1)), and a full witness table uses O((n+1)(B+1)) cells.
Keeping only the last row fails because p may point far back. This becomes
the capstone's changed-requirement task.
When bounds dominate. A capacity of 10^12 stored in a few bytes does not make an n-by-capacity table reasonable. With a small item count, subset enumeration or meet-in-the-middle may be better; with a small total nonnegative value, a value-indexed formulation may help. Each needs its own assumptions, cost and output analysis. Do not claim a solver scales to a fixed number of variables independently of model structure and hardware.
Common Confusion / Misconceptions
NP-hardness does not prove that no polynomial algorithm exists unconditionally, nor that all small or structured instances are hard in practice. A failed greedy rule does not force a unique replacement. Randomization does not imply approximate answers: Las Vegas algorithms preserve correctness while runtime is random. Approximation algorithms have stated guarantees; heuristics may not. Neither label excuses changing an exact contract without saying so.
How To Use It
Write a decision record with the contract, one tiny counterexample to a tempting wrong approach, the chosen state/proof, state and transition bounds, estimated representation cost, and verification plan. Add a changed assumption and explain which part breaks. Benchmark only after the model and cost analysis are sound; report environment, workload, included work and uncertainty.
Check Yourself
When does a smaller input count still hide a huge numeric state dimension? Which capstone constraint invalidates the original prefix state? What distinguishes an approximate guarantee from an unmeasured heuristic?
Mini Drill or Application
Two nonoverlapping jobs each cost 2 and profit 3; one spanning job costs 1 and profit 5. Budget is 2. Feedback: unbudgeted scheduling picks the pair for 6; budgeted scheduling must pick the spanning job for 5. State exactly why a time-compatible plan can still be infeasible.
Read This Only If Stuck
Skiena: algorithm design and state-space limits. Use the capstone to produce a concrete decision record instead of adding another untested pattern.