optional · interactive figures

24

Explore: rounding and primal–dual

Threshold rounding with the threshold in your hands, primal–dual set cover raising one dual at a time, and Jain–Vazirani's clock on a line.

optional: nothing in the lab depends on itback to the slides

24 · explore

Threshold rounding, with t on a slider

Try: raise t just above ½ on each instance; switch to the triangle with a tail, whose LP mixes 0, ½ and 1. Static version: rounding a weighted 5-cycle.

24 · explore

Primal–dual set cover, one raise at a time

Try: step through and watch each raise stop exactly when some set's bar is full. Static version: primal–dual set cover, traced.

24 · explore

Jain–Vazirani's clock, on a line

Try: drag the time slider from 0 to 6 and watch A open at 3.5 and B at 5. Static version: Jain–Vazirani on a line.