4810-1183 Approximation and Online Algorithms with Applications
Lecture Note 8: Online Algorithm for Secretary Problem
Problem Definition
Let us consider the situation when we have a number of persons applying for a secretary position at ourcompany. We will interview each applicants one by one, and, after the interview, we will give eachapplicant his/her score. We want to select an applicant with the largest score. However, we have to tell
all applicants if we will hire them immediately after the interview. We cannot continue the interviews
after we accept to hire an applicant, and we cannot hire someone whom we have rejected before.
We will call this problem as the “secretary problem”. Its optimization model is as follows:
Input:

Score of each applicant 𝑠1 , … , 𝑠𝑛

Output:Decision if we select each applicant 𝑑1 , … , 𝑑𝑛 ∈ {Yes, No}

Constraint:

1) only one 𝑑𝑖 is Yes.
2) 𝑑𝑖 is decided based on only 𝑠1 , … , 𝑠𝑖

Objective Function:

Maximize the score of the selected participant

On last week, we have introduce an online strategy for the ski rental problem. The strategy is2-competitive, that is 𝑆𝑂𝐿𝐼 ≤ 2 ⋅ 𝑂𝑃𝑇𝐼 for all possible input 𝐼 . As the secretary problem is amaximization problem, if we work on the competitive ratio, the competitive ratio 𝛼 must be smaller
than 1. A strategy is 𝛼-competitive if 𝑆𝑂𝐿𝐼 ≥ 𝛼 ⋅ 𝑂𝑃𝑇𝐼 for all possible input 𝐼.
However, as discussed in the previous lecture note, the competitive ratio is not the only way tojustify an online algorithm. We will introduce another justification in this lecture note. That is “theprobability that we will have an optimal solution”.
Let us now assume that the interview order of the applicants is random. When we have 3applicants, there are 6 possible orders:
1.
2.
3.
4.
5.
6.

𝑠1 > 𝑠2 > 𝑠3 ,𝑠1 > 𝑠3 > 𝑠2 ,𝑠2 > 𝑠1 > 𝑠3 ,𝑠2 > 𝑠3 > 𝑠1 ,𝑠3 > 𝑠1 > 𝑠2 ,𝑠3 > 𝑠2 > 𝑠1 .

We assume that the probability of having each of the above order is 1/6. When we have 𝑛 applicants,
we will have 𝑛! orders and the probability of having each order is 1/𝑛!.
When the goal of online algorithms is “the probability of having an optimal solution”, theassumption in the previous paragraph is usually essential. We usually can find some probabilistic
distribution on our input that makes the probability very small.
Strategy
By the assumption in the previous section, if we always choose the first applicants. The score of ourselected participant is 𝑠1. When the number of applicants is 3, 𝑠1 is the largest value with probability111(order 1) + 6 (order 2) = 3. When the number of applicants is 𝑛, we will have the optimal value
6with probability 1/𝑛, which might be too less.

Let us consider the following strategy:
1: maxValue = 0
2: For i = 1 to n:
3:
if i <= n/e:4:d[i] = false
5:
maxValue = max(s[i], maxValue)
6:else if i = n:7:d[i] = true
8:else if s[i] > maxValue:
9:d[i] = true
10:d[j] = false for all j > i
11:
break

We will not select the first 𝑛/𝑒 applicants regardless of their scores. They are chosen to be a benchmarkof our selection. We will find the maximum among their scores, and, if a score of a later applicants islarger than the maximum, we will select his/her. If none of the later applicants has a larger score, wewill choose the last applicant.
Let now work on the case of 3 applicants. There,𝑛3= ≈ 1. We will never select the first𝑒𝑒

applicant, and will use his/her score 𝑠1 as a benchmark. Recall the 6 cases in the previous page. The
score of the second applicants, 𝑠2, is larger than the benchmark 𝑠1, in case 3, 4, and 6. We choose thesecond applicant on that case, and we choose the third applicant on the others. We will have the largest
1

score in case 3, 4, and 5, which make the probability of having an optimal solution be 2. This increases
1from that of the trivial strategy, 3.
Analysis
We have shown that the success probability is 1/2, when 𝑛 = 3. In this section, we will show
1𝑒that, for any 𝑛, the success probability is no less than ≈ 0.36.
With probability 1/𝑒, the best applicant is among the first 𝑛/𝑒 applicants. Because the selectedparticipants will not be in the first 𝑛/𝑒 applicants, the best participant will not be selected. Our strategy
will fail to find the best applicant in this case.
Now, let us suppose that the best participant is the 𝑚th participant such that 𝑚 > 𝑛/𝑒. There
are 𝑚 − 1 participants before the participant. Consider the figure in the following page. We will notselect the 𝑚th participant when there is some applications in the orange zone have a higher score than
all the first 𝑛/𝑒 aplicants.
Let us consider the first two zones (blue and orange) as a subarray of the array of all scores. If
the largest score in the subarray is in the first zone, we will never select an applicant from the orangezone. We will interview the 𝑚th participant, and, as he/she has a higher score than everyone in the firstzone, he/she will be selected. Our algorithm can find an optimal solution, which is the 𝑚th participant.
On the other hand, if the largest score in the subarray is in the second zone, an applicant withthe largest score or someone in the orange zone will be selected. Our algorithm will fail to find an
optimal solution.
When we have a random order, a subarray of the order will be also random. Because of that,the order of the 𝑚 − 1 predecessors is also random. The probability that we have the largest in the𝑛subarray in the first 𝑛/𝑒, which is also the success probability, is ( 𝑒 )/(𝑚 − 1).

We know that the success probability equal 𝑃1 + ⋯ + 𝑃𝑛 when 𝑃𝑖 is the probability that the best
applicant is the 𝑖 th applicant and he/she is selected. It is clear from the definition that 𝑃𝑖 = 0 for 𝑖 ≤ 𝑛/𝑒.
For 𝑖 > 𝑛/𝑒, the probability of having 𝑚 equal a particular number 𝑖 is 1/𝑛, and, by the previous𝑛paragraph, the success probability when 𝑚 = 𝑖 is ( 𝑒 ) /(𝑖 − 1). Thus, we know that the successprobability is𝑛𝑛𝑛−111111 1 𝑛11𝑛1𝑒∑ ⋅= ∑= ∑ ≈ ∫ 𝑑𝑖 = [ln 𝑛 − ln ] = [ln 𝑛 − (ln 𝑛 − ln 𝑒)]
𝑛 𝑖−1 𝑒 𝑛 𝑖−1 𝑒 𝑛 𝑖 𝑒 𝑛 𝑖𝑒𝑒𝑒𝑛𝑛𝑖= +1𝑒𝑖= +1𝑒

1= .
𝑒

𝑖=𝑒𝑒

Online Navigation Summaries
Let us suppose that we have a drone that will take a video which consist of a million of images, and wewant to find the meaning of the video by a machine learning algorithm. It is usually very hard to makesense of a large number of images, so we want to select the most meaningful images out of them. We
call the problem “navigation summaries”. In the following footage, we may select the image highlighted
in blue. They tell us that the video were taken at a place with a bicycle and a gate.

When a video is as long as hours and it is broadcasted at a social network, users might want tohave a part of summary before the end of the broadcasting. Also, a drone might want to place a sensor
at important places to watch the change at there. It would be more efficient if the drone can place thesensor just after a photo is taken.
The authors of [2] propose a way to measure an “importance” of each picture. They assume
that we will select at most 𝑘 images from the video. By that, the optimization model for the online
navigation summaries is as follows:
Input:

Importance of each image 𝑠1 , … , 𝑠𝑛
Number of selected images 𝑘

Output:Decision if we select each image 𝑑1 , … , 𝑑𝑛 ∈ {𝑌𝑒𝑠, 𝑁𝑜}

Constraint:1) The number of selected images is 𝑘2) For all selected images 𝑖, 𝑠𝑖 is one of the 𝑘 largest scores.
3) 𝑑𝑖 is decided based only on 𝑠1 , … , 𝑠𝑖

Objective Function:

None

We want to satisfy the second constraint with as high probability as possible. The authorsdevise an algorithm based on the strategy in the following page.

1: threshold = 0
2: For i = 1 to n:
3:
if i <= r:4:d[i] = false
5:
threshold = max(s[i], maxValue)
6:else if i = n - k + (number of selected sensors) + 1:
7:d[i] = true
8:else if s[i] > maxValue:
9:d[i] = true
10:
if we have already selected k images:
11:d[j] = false for all j > i
12:
break

The only difference between the first and the second algorithm is: we do not stop after an image isselected, but wait until we have selected 𝑘 images. We previously set 𝑟 to 𝑛/𝑒, and, actually, the value
maximize the success probability. We are going to calculate at the following paragraph the best value
for 𝑟 in this application.
Let us consider the figure at the previous page again. For each 𝑟 < 𝑚 ≤ 𝑛, we will calculate
the probability that:
1. 𝑠𝑚 is one of the top 𝑘 score;
2. before 𝑚, 𝑘 − 1 correct images are selected;
3. 𝑚 is selected in the above algorithm.
By the random order, the probability of having 1) is 𝑘/𝑛. Then, for 2), by our algorithm, we must have𝑛𝑚−1−𝑟
𝑘 – 1 images of the top 𝑘 in the second zone. The probability of having that is ()/().
𝑘−1
𝑘−1
For 3), we must be sure that other than the 𝑘 − 1 images in 2), the next largest score in the first and thesecond zone must be in the first zone. Otherwise, we will choose that next best image. That is, the 𝑘thlargest score in the first 𝑚 − 1 images is in the orange zone. With the assumption that the score orderis random, we know that the probability is 𝑟/(𝑚 − 1).
𝑚−1−𝑟𝑘 ( 𝑘−1 )𝑟
To conclude, the probability that we have 𝑚 satisfying the three conditions is 𝑛 ⋅⋅ 𝑚−1.
𝑛()𝑘−1

The probability that having some 𝑚 satisfying the conditions is then equal to𝑚−1−𝑟𝑘 ( 𝑘−1 )𝑟∑ [ ⋅⋅].
𝑛𝑛
𝑚−1()
𝑚=𝑟+1
𝑘−1
𝑛

By experiment, the authors show that the value of 𝑟 that maximizes the probability can be approximated𝑛by the value 1 .
𝑘𝑒 𝑘

In practice, if we just aim to choose the maximum scores, we might have a lot of images withthe same object. The authors of the paper have a heuristic to avoid that. They do not around 2 selected
images to be closer than a specific time frame.
Exercises
We will introduce the concept of randomized algorithm to the secretary problem. We will select thesecretary 𝑖 with probability 𝑖/𝑛, if 𝑠𝑖 is the largest among 𝑠1 , … , 𝑠𝑖 .
Question 1: Discuss why the probability that we choose applicant 1 is 1/𝑛. Also, discuss why theprobability that we correctly choose applicant 1 is 1/𝑛2.

𝑛−1

Question 2: Discuss why the probability that we choose applicant 2 is 𝑛2 . Also, discuss why the2probability that we correctly choose applicant 2 is 𝑛 ⋅ (𝑛 − 1)/𝑛2 .
Question 3: Discuss why the probability that we choose applicant 3 is (𝑛 − 1)2 /𝑛3. Also, discuss why3the probability that we correctly choose applicant 3 is ⋅ (𝑛 − 1)2 /𝑛3.
𝑛Question 4: From your answer of Question 1 –3, guess what the success probability of this strategy is.
𝑛−1 𝑚) ⋅ 𝑚] = (𝑛 − 1)𝑛1−𝑛 [𝑛𝑛 − 2(𝑛 − 1)𝑛 ].
𝑛Question 5: Given ∑𝑛𝑚=1 [(Write your success probability Question 4 in a form without summation.
𝑛−1 𝑛2Question 6: Given lim 1 − 2 [ 𝑛 ] = 1 − 𝑒. Discuss why this strategy is not better than the strategy𝑛→∞discussed in the class.
Construct 10,000 arrays of size 𝑛 with random permutations, and test an algorithm for the secretary
problem on those arrays.
Question 7: What is the success probability of your algorithm when 𝑛 = 100?
Question 8: Plot the relationship between 𝑛 and the success probability.
Question 9: From the plot, what is relationship between 𝑛 and the success probability?
References[1] T. S. Ferguson, “Who solved the secretary problem?”, Statistical Science, Vol. 4, No. 3, pp. 282289, 1989.
[2] Y. Girdhar, G. Dudek, “Online navigation summaries”, Proceeding of the 2010 IEEE International
Conference on Robotics and Automation (ICRA 2010), pp. 2035-2040, 2010.