Randomized roundingRandomized rounding – contd.Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10ExRandomized rounding – contd.ercisesSlide 12Slide 13Slide 14Randomized rounding1Randomized rounding – contd.We can solve the LP relaxation by any LP algorithm, which generally results in variable assignments that are between 0 and 1. The next step is to round the variables to 0/1 values. This could be done deterministically as usual rounding, but then in a pessimistic case too much violation of the constraints can occur. For example, assume the problem contains the following constraint: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 to one, so the lefthand-side becomes 1000.2Randomized rounding – contd.3Randomized rounding – contd.4Randomized rounding – contd.5Randomized rounding – contd.6Randomized rounding – contd.7Randomized rounding – contd.8Randomized rounding – contd.9Randomized rounding – contd.Remark: The approach is most useful if the problem contains “soft" constraints. What are these? It is customary to differentiate two types of constriants:Hard constraints: these must be obeyed. For example, they may represent some physical law which is impossible to violate.Soft constraints: these can possibly be violated if there is no other way to solve the problem, but then we have to pay a penalty, so we would like to minimize the violation. For example, budget constraints often behave this way.Since randomized rounding may result in constraint violation, it is typically good for soft constraints.10ExRandomized rounding – contd.ercisesIf we can guarantee an error bound B with probability p, then how many repetitions are needed if we want to decrease the error bound by a factor of10, while keeping the same probability?11Randomized rounding – contd.12Randomized rounding – contd.13Randomized rounding –
View Full Document
Unlocking...