Randomized Algorithms Hiring Problem R. Inkulu http://www.iitg.ac

Randomized Algorithms
Hiring Problem
R. Inkulu
http://www.iitg.ac.in/rinkulu/
(Randomized Algorithms)
1 / 10
Outline
1
Hire the best
2
Hire the first best after the kth candidate
3
Generating uniform random permutation
(Randomized Algorithms)
2 / 10
Randomized Algorithm to hire an assistant
(1) randomly permute the list of candidates given in array A
(2) best = 0 ← candidate 0 is a least-qualified dummy candidate
(3) for i = 1 to n
(a) interview candidate A[i] ← small cost ci
(b) if A[i] has the better score than the current best candidate
(i) best = i
(ii) hire candidate i
← high cost ch
Since the above randomized algorithm always picks the best candidate
(correct in terms of the objective function), it is termed as the Las Vegas
algorithm.
(Randomized Algorithms)
3 / 10
Expected hiring cost
• Assume that every permutation of candidates is equally probable.
• Let X be the random variable whose value equals the hiring cost. The
expected value of X, denoted with E[X], is the required.
For i = 1, . . . , n, let Xi denote the random variable whose value equals
the cost involved in hiring ith candidate.
E[Xi ] =
ch
i ;
and from the linearity of expectation E[X] = O(ch lg n)
• The expected cost in total is O(ci n + ch lg n).
Analysis is same as in the case of finding average-cost except that the
assumption about input distribution is replaced with the above mentioned one.
The following algorithm shows that there is no need of this assumption either.
(Randomized Algorithms)
4 / 10
Outline
1
Hire the best
2
Hire the first best after the kth candidate
3
Generating uniform random permutation
(Randomized Algorithms)
5 / 10
Algorithm that takes k and n as input
(1) randomly permute the list of candidates given in array A
(2) find the bestscore among the first k candidates
(3) hire the first best candidate from k + 1 to n whose score is greater than the
bestscore
(4) (otherwise,) hire the nth candidate
here the objective is to choose a k so that the hired candidate is the best among
all the n candidates
(Randomized Algorithms)
6 / 10
Analysis
Assuming that every permutation of candidates is equally probable, the
analysis is same as in probabilistic analysis of deterministic algorithm: the
probability of hiring the best-candidate is maximized when k = ne ; for this k
value probability of hiring the best candidate is at least 1e .
Since there is a non-zero probability of picking a non-best candidate, the
above randomized algorithm is said to be a Monte Carlo algorithm.
(Randomized Algorithms)
7 / 10
Outline
1
Hire the best
2
Hire the first best after the kth candidate
3
Generating uniform random permutation
(Randomized Algorithms)
8 / 10
Algorithm to randomly permute the list of candidates
(1) for i = 1 to n
(i) swap A[i] with A[rand(i, n)]
• The rand(i, j) function is assumed to output any integer in [i, j] with
probability
1
j−i+1
• The challenge is to ensure that this algo produces uniform random
permutation i.e., every permutation of candidates is equally possible with
probability n!1
(Randomized Algorithms)
9 / 10
Proving that the above algo outputs uniform random
permutation
Invariant: Just prior to the ith iteration of the for loop, for each possible
(i − 1)-permutation of the n elements, the subarray A[1 . . . i − 1] contains this
(i − 1)-permutation with probability (n−i+1)!
.
n!
(Randomized Algorithms)
10 / 10

Download Report