1 Outline Slide 1 Randomized rounding methods 2 Randomized rounding Solve c x subject to x 2 P for arbitrary c. x be optimal solution. From x create a new random integer solution x, feasible in P : Ec x] = ZLP = c x . ZLP ZIP EZH ] = ZLP : Hence, P integral. 0 Slide 2 0 0 2.1 Minimum s ; t cutX minimize subject to Slide 3 cuv xuv u vg2E xuv yu ; yv xuv yv ; yu ys = 1 yt = 0 yu xuv 2 f0 1g: f fu vg 2 E fu vg 2 E 2.1.1 Algorithm Solve linear relaxation. Position the nodes in the interval (0 1) according to the value of yu . Generate a random variable U uniformly in the interval 0 1]. Round all nodes u with yu U to yu = 0, and all nodes u with yu > U to yu = 1. Set xuv = jyu ; yv j for all fu vg 2 E. Slide 4 2.2 Theorem Slide 5 For every nonnegative cost vector c, EZH ] = ZIP = ZLP : 1 U yv is rounded to 1 yu is rounded to 0 yt Proof: yu yv ys 2 3 X cuv xuv 5 ZIP EZH ] = E 4 fu vg2E ; X ; = cuv P min yu yv U < max yu yv fu vg2E X cuv jyu ; yv j = fu vg2E = ZLP ZIP 2.3 Stable matching n men fm1 : : : mn g and n women fw1 : : : wng, with each person having a list of strict preference order. Find a stable perfect matching M of the men to women: There does not exist a man m and a woman w who are not matched under M , but prefer each other to their assigned mates under M . 2.3.1 Formulation w1 >m w2 if man m prefers w1 to w2 . m1 >w m2 if woman w prefers m1 to m2 . Decision variables 1 if m is matched to w , i j xij = 0 otherwise. 2 Slide 6 Slide 7 N = f1 : : : ng n X xij = 1 i 2 N xij = 1 i=1 xij 2 f0 1g j 2 N j=1 n X xij + X fkjwk 0, then X xij + k wkwj mi g kj 1 i j 2 N ij and ij = xij for all i j 2 N : feasible if ij = xij and x 2 PSM . Objective Slide 9 x 2 PSM n X n X j ; ij i=1 j=1 i=1 j=1 X s.t. i + j ; ik ; max xkj = 1: f j f j Dual X xik + X fkjmk wj mi g f j f j wj 1 0 0 0 1 1 1 0 2.4 Key Theorem Slide 10 PSM = conv(S): 2.4.1 Randomization Generate a random number U uniformly in 0,1]. Match mi to wj if xij > 0 and in the row corresponding to mi , U lies in the interval spanned by xij in 0 1]. Accordingly, match wj to mi if in the row corresponding to wj , U lies in the interval spanned by xij in 0 1]. Key property: xij > 0, then the intervals spanned by xij in rows corresponding to mi and wj coincide in 0 1]. The matching is stable: wk who is preferred by mi to his mate wj under the as- signment, i.e., the interval spanned by xik is on the right of the interval spanned by xij in the row corresponding to mi , is assigned a mate whom she strictly prefers to mi , since in the row corresponding to wk the random number U lies strictly to the left of the interval xik . xUij = 1 if mi and wj are matched. ExUij ] = P(U lies in the interval spanned by xij ) = xij : R1 u x du: x can be written as a convex combination of stable matchings 0 ij xu as u varies over the interval 0 1]. xij = 4 Slide 11 Slide 12