Content deleted Content added
m edit wording for parallelism |
Erel Segal (talk | contribs) No edit summary |
||
Line 1:
In [[mathematics]] and [[computer science]], the '''method of conditional probabilities''' {{harv|Spencer|1987}}, {{harv|Raghavan|1988}} is a method for constructing efficient [[Deterministic algorithm|deterministic]] [[approximation algorithms]], based on the [[probabilistic method]].
In [[mathematics]] and [[computer science]], the [[probabilistic method]] is used to prove the existence of mathematical objects with desired combinatorial properties. The proofs are probabilistic — they work by showing that a random object, chosen from some probability distribution, has the desired properties with positive probability. Consequently, they are [[nonconstructive proof|nonconstructive]] — they don't explicitly describe an efficient method for computing the desired objects.▼
▲
The '''method of conditional probabilities''' {{harv|Spencer|1987}}, {{harv|Raghavan|1988}} converts such a proof, in a "very precise sense", into an efficient [[deterministic algorithm]], one that is guaranteed to compute an object with the desired properties. That is, the method [[derandomization|derandomizes]] the proof. The basic idea is to replace each random choice in a random experiment by a deterministic choice, so as to keep the conditional probability of failure, given the choices so far, below 1.▼
▲The
The method is particularly relevant in the context of [[randomized rounding]] (which uses the probabilistic method to design [[approximation algorithm]]s).
| |||