Living with NP-Hardness: Approximation and Heuristics · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.
En anglais

Good answers without perfect ones

Computing · Algorithms & Data Structures · ages 21-22
Name ______________________   Date ____________

  1. What separates an approximation algorithm from a heuristic without a proved quality bound?

    • It must return an exact optimum on small inputs
    • It has a proved solution-quality bound
    • It must run faster on every measured input

  2. What would a polynomial-time exact algorithm for an NP-hard optimization problem imply?

    • P=NP
    • Every instance is difficult
    • Exact algorithms cannot exist

  3. Two edges in the matching used by the vertex-cover algorithm may share an endpoint.

    Circle one:   True   False

  4. On an input in its stated domain, a 1.5-approximation minimizes route length. The optimum is 80 and its feasible route has length 110. Is this consistent with the guarantee?

    • No; its route must have length exactly 80
    • No; its route must have length exactly 120
    • Yes; 110 is at most the upper bound 120

  5. A maximal matching contains 4 edges. The algorithm selects both endpoints of each matched edge. How many vertices does it select?

    Answer: ______________

  6. A minimization task needs a result by Friday and a proved factor-2 bound. The exact solver misses Friday. An applicable factor-2 approximation finishes Thursday. A heuristic finishes today but has no quality bound. Which meets both requirements?

    • The exact solver that misses Friday
    • The applicable factor-2 approximation
    • The fast heuristic with no quality bound

  7. A vendor tests a scheduler on a non-exhaustive sample, observes costs usually within 5 percent of optimum, and claims a 1.05-approximation over all valid inputs. What is missing?

    • A rule that every trial must reach the optimum
    • A requirement that all valid inputs be equally large
    • A proof of the bound over the stated domain

  8. A classmate says the vertex-cover method needs a largest possible matching. Which condition actually makes the selected endpoints cover every edge?

    • No further disjoint edge can be added
    • Every graph vertex belongs to the matching
    • The matching uses the fewest possible edges
LightMySky · lightmysky.comW1-mt_tZ82ty6h2u-s1

Answer key

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

Good answers without perfect ones W1-mt_tZ82ty6h2u-s1

  1. It has a proved solution-quality bound · An approximation has a proved quality bound over its stated domain. A heuristic may have other guarantees without having that bound.
  2. P=NP · Such an algorithm would yield polynomial-time solutions to NP problems through reductions. Whether P=NP remains unresolved.
  3. False · Matching edges have disjoint endpoints. After choosing an edge, the algorithm removes all edges touching either endpoint.
  4. Yes; 110 is at most the upper bound 120 · The bound is 1.5 times 80, or 120. A feasible route of length 110 is within that bound; equality is not required.
  5. 8 · The four edges have disjoint endpoints, so they contribute exactly 4 times 2, or 8, distinct vertices.
  6. The applicable factor-2 approximation · The approximation has the required proof and finishes before Friday. The other methods each fail a stated requirement.
  7. A proof of the bound over the stated domain · The trials describe sampled performance. They do not establish a factor-1.05 bound for every valid input.
  8. No further disjoint edge can be added · That condition is maximality. An uncovered edge would be disjoint from all matched edges and could be added, contradicting it.
Worksheet · LightMySky