Randomized RoundingThe randomized rounding technique works the best when the ILP is of combi-natorial nature, that is, a 0-1 programming problem. The principle is shownvia the following example. Consider the problemmax Z = cxsubject toAx = bxi∈ {0, 1}, i = 1, . . . , nReplace the last constraint with 0 ≤ xi≤ 1. The new problem is already anLP, called the LP relaxation of the 0-1 program.We can solve the LP relaxation by any LP algorithm, which generally re-sults in variable assignments that are between 0 and 1. The next step is toround the variables to 0/1 values. This could b e done deterministically asusual rounding, but then in a pessimistic case too much violation of the con-straints can occur. For example, assume the problem contains the followingconstraint:x1+ x2+ . . . + x1000= 510 (1)and the LP solution is x1= . . . = x1000= 0.51, which satisfies the constraint.If we round the variables in the usual way, then they all will be rounded toone, so the lefthand-side becomes 1000.One the other hand, we can have much smaller violation of the constraints byrounding randomly, according to the following rule. The randomly roundedvalueexiof xiwill be:exi=1 with probability xi0 with probability 1 − xiThis can be easily implemented by drawing a uniformly distributed randomnumber yi∈ [0, 1] and setting xi= 1 if xi≥ yi, otherwise xi= 0.What is the advantage of the random rounding? We can observe that theexpected value ofex1+ . . . +ex1000will be exactly 510, thus it satisfies theconstraint. Of course, the actual value may still violate it, but one canexpect that the actual values fluctuate around the average, so the errors ofdifferent signs largely cancel out if there are many variables.One can quantitatively estimate the error that can still occur with a cer-tain small probability. The way of this estimation is shown in the followingtheorem (informal explanation follows after the theorem).Theorem 1. Let x be an n-dimensional vector with 0 ≤ xi≤ 1 for all i.Assume x satisfies the constraint ax = b. Let ˜x be the rounded version of x,obtained by randomized rounding. Then the following inequality holdsb − amaxqαn log n ≤ a˜x ≤ b + amaxqαn log nwith probability at least 1 − n−α, where α > 0 is any constant and amax=maxi|ai|.The Theorem says that the error, which is the deviation of the actual valueof a˜x from the expected value b, is bounded by amax√αn log n. This may bemuch smaller than b.Observe the effect of the α parameter. The bound on the error holds withprobability at least 1 − n−α. If α is large, then this probability is very closeto 1. Then, however, the error amax√αn log n gets also larger. If α is small,then the error is small, but it holds with smaller probability. Thus, thereis trade-off between providing a tighter bound less surely or a looser boundmore surely. Note, however, that this plays a role only in the analysis, notin the actual algorithm.Let us look at example (1) we used. Choose α = 1. The other parametersare:n = 1000, amax= 1, b = 510The error term will be:amaxqαn log n =q1000 log 1000 ≈ 83and the probability is1 − n−α= 1 − 1000−1= 0.999 = 99.9%.Thus we obtain that the deviation from the required ax = 510 is bounded as427 ≤ a˜x ≤ 593with 99.9% probability, thus, almost surely. In contrast, with deterministicrounding we could only say that the value is between 0 and 1000.What if we are satisfied with less certainty, say, with 90% probability? Thenwe can choose α = 1/3, since 1 − 1000−1/3= 0.9 and then we get the errorbound ofamaxqαn log n =s13· 1000 log 1000 ≈ 48.This yields the tighter estimation462 ≤ a˜x ≤ 558 (2)which holds, however, only with 90% probability.What if we would like to have the tighter bound (2) but also the higher 99.9%probability? There is a way to achieve that, too. Repeat the randomizedrounding 3 times independently. Then in each trial the probability of violat-ing (2) will b e at most 10%. Hence the probability that all the 3 independenttrials violate (2) is 0.13= 0.001 = 0.1%. Thus, among the 3 trials there mustbe one with 99.9% probability that satisfies the bound (2), so we can choosethis one. The moral is that we can “amplify” the power of the method byrepeating it several times independently and then choosing the best result.The Theorem can directly be extended to the case that involves repeatedindependent trials. With r repetitions the probability is amplified to 1−n−αr,while the error bound remains the same.Remark: The approach is most useful if the problem contains “soft” con-straints. What are these? It is customary to differentiate two types of cons-triants:• Hard constraints: these must be obeyed. For example, they may rep-resent some physical law which is impossible to violate.• Soft constraints: these can possibly be violated if there is no other wayto solve the problem, but then we have to pay a p enalty, so we wouldlike to minimize the violation. For example, budget constraints oftenbehave this way.Since randomized rounding may result in constraint violation, it is typicallygood for soft constraints.Exercises1. If we can guarantee an error bound B with probability p, then how manyrepetitions are needed if we want to decrease the error bound by a factor of10, while keeping the same probability?Answer: If we use r repetitions, then the probability bound is amplified to1 − n−αr. For keeping the original probability we can choose a new α asα0= α/r. Then the error will decrease by a factor of√r, as α is under thesquare root in the expression of the error. Thus, if we want to decrease theerror by a factor of 10, then we need 100 repetitions.better solution via randomized rounding than with naive deterministic round-ing, especially if there are many variables.2. Generalize Theorem 1 for the case when there are more constraints.Answer: Theorem 1, when applied to several constraints, implies the theorembelow, via the union bound of probabilities. The union bound says that forany events A1, A2, . . . Am, the probability of their union (i.e., the probabilitythat at least one of them occurs) is bounded by the sum of their individ-ual probabilities, no matter whether the events are independent or not. Informula:Pr(A1∪ . . . ∪ Am) ≤ Pr(A1) + . . . + Pr(Am).Theorem 2. Let x be an n-dimensional vector with 0 ≤ xi≤ 1 for all i.Assume x satisfies Ax = b, representing m constraints. Let ˜x be the roundedversion of x,
View Full Document
Unlocking...