Linear Programming, Duality and Rounding · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Fractions first, decisions after

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

  1. How do you relax vertex cover to a linear program?

    • Delete every second edge from the graph
    • Replace each 0 or 1 with a fraction between 0 and 1
    • Square every variable to smooth the program

  2. What does a linear program need?

    • Variables for choices, linear limits, and a linear goal
    • A guess at the answer and nothing else
    • Curved limits with a squared goal

  3. The relaxed fractional optimum bounds the integer optimum from below.

    Circle one:   True   False

  4. A fractional vertex cover optimum costs 6. Rounding at one half at most doubles the cost. What is the worst cost the rounded cover can have?

    Answer: ______________

  5. A dual solution certifies your primal answer is within 5 percent of optimal. What did the dual give you?

    • The exact integer optimum itself
    • A rounding rule for the fractions
    • A certificate for a bound, without knowing the optimum

  6. Why does rounding at one half keep every edge covered?

    • Every edge holds two endpoints summing to at least 1, so one rounds up
    • Rounding up always deletes the cheaper endpoint
    • Halves are lucky numbers for graphs

  7. A student rounds fractions down to 0 to save money and drops some edges. What is the error?

    • Rounding down is always optimal for covers
    • A cover must cover every edge; uncovered edges break feasibility whatever they save
    • Dual certificates forbid all rounding

  8. Primal rounded cost is 11 and a dual solution certifies no answer beats 10. What can you claim?

    • The rounded answer is optimal, since 11 is near 10
    • The rounded answer is within a factor of 1.1 of optimal
    • Nothing, since primal and dual disagree
LightMySky · lightmysky.comW1-mt_rsj6G8iydV-s1

Answer key

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

Fractions first, decisions after W1-mt_rsj6G8iydV-s1

  1. Replace each 0 or 1 with a fraction between 0 and 1 · Fractions widen the options, making the program solvable.
  2. Variables for choices, linear limits, and a linear goal · Linear choices, linear limits, linear goal: all three, all linear.
  3. True · Wider options can only improve the best achievable value.
  4. 12 · Doubling 6 caps the rounded answer at 12.
  5. A certificate for a bound, without knowing the optimum · Any feasible dual value bounds the primal from the other side.
  6. Every edge holds two endpoints summing to at least 1, so one rounds up · Cover limits force the pair sum up, and halves tip one endpoint over.
  7. A cover must cover every edge; uncovered edges break feasibility whatever they save · Cheap and uncovered is not a cover at any price.
  8. The rounded answer is within a factor of 1.1 of optimal · Eleven against a floor of 10 bounds the gap without naming the optimum.
Worksheet · LightMySky