Good Answers Without Perfect Ones

Computing · Algorithms & Data Structures · ages 21-22

Name ______________________ Date ____________

What separates an approximation algorithm from a heuristic?
- Approximations run only on small inputs
- Approximations carry a proved ratio while heuristics carry no promise
- Heuristics never produce good answers
A problem is NP-hard. What does that rule out?
- An exact method that runs fast on every input
- Any useful answer for large inputs
- Testing a method on real data
In the vertex cover 2-approximation, the matched edges may share vertices.
Circle one: True False
A routing tool guarantees a route never longer than 1.5 times the shortest, on every input. What is it?
- An exact method in disguise
- A heuristic with confident marketing
- An approximation with ratio 1.5
Your matching holds 4 edges. At most how many vertices enter the cover?
Answer: ______________
A huge network must be handled by Friday, and the contract demands a result within twice the optimum. What do you choose?
- An exact method stretched past the deadline
- An approximation with a proved factor of 2
- A heuristic because it feels quick
A vendor reports its scheduler usually lands within 5 percent of optimum and calls it a 1.05-approximation. What is the mistake?
- Schedulers cannot be measured at all
- Five percent is too small a gap to matter
- Measurements report the past but prove no promise for every input
A classmate says the factor of 2 holds because the matching built is the largest possible. What is wrong?
- The factor comes from each matched edge needing a distinct optimum vertex, not from a largest matching
- The cover must contain every vertex of the network
- Matchings are banned from approximations

Answer key

For grown-ups. Fold this page away before handing over the rest.

Good Answers Without Perfect Ones W1-mt_tZ82ty6h2u-s1

Approximations carry a proved ratio while heuristics carry no promise · The ratio is a promise for every input. A heuristic offers measurements instead.
An exact method that runs fast on every input · Hardness closes one door: exact and fast everywhere. Approximation and heuristics stay open.
False · A matching means no shared vertices. That separation is what the factor of 2 rests on.
An approximation with ratio 1.5 · A promise for every input is the mark of an approximation. Marketing words change nothing.
8 · Both ends of each matched edge enter, so 4 edges give at most 8 vertices.
An approximation with a proved factor of 2 · Huge input rules out exact, and the contract demands a promise, which only the approximation gives.
Measurements report the past but prove no promise for every input · Usually is a measurement claim. An approximation needs a ratio proved for every input.
The factor comes from each matched edge needing a distinct optimum vertex, not from a largest matching · Any matching gives the factor. Each matched edge forces a separate optimum vertex, so the optimum is at least the matching size.