CMS57opmtr cince Week 9:Online Algorithms Instructor:Shengyu Zhang 1
Instructor: Shengyu Zhang 1
Secretary hiring problem 2
Secretary hiring problem 2
A motivating problem ■Secretary problem: We want to hire a new office assistant. There are a number of candidates. We can interview one candidate each day,but we have to decide the acceptance/rejection immediately. 3
A motivating problem ◼ Secretary problem: ❑ We want to hire a new office assistant. ❑ There are a number of candidates. ❑ We can interview one candidate each day, but we have to decide the acceptance/rejection immediately. 3
One possible strategy On each day,if candidate A is better than the current secretary B,then fire B and hire A. Each has a score.Assume no tie. Firing and hiring always have overhead. Say:cost c. We'd like to pay this but it'll be good if we could have an estimate first. Question:Assuming that the candidates come in a random order,what's the expected total cost?
One possible strategy ◼ On each day, if candidate 𝐴 is better than the current secretary 𝐵, then fire 𝐵 and hire 𝐴. ❑ Each has a score. Assume no tie. ◼ Firing and hiring always have overhead. ❑ Say: cost 𝑐. ◼ We’d like to pay this but it’ll be good if we could have an estimate first. ◼ Question: Assuming that the candidates come in a random order, what’s the expected total cost? 4
Probability... Define a random variable X X=#of times we hire a new secretary Our question is just to compute E[cX]=c·E[X]. By definition, E[X]=∑x=1x·Pr[X=x]. But this seems complicated to compute. 5
Probability… ◼ Define a random variable 𝑋 𝑋 = # of times we hire a new secretary ◼ Our question is just to compute 𝐄 𝑐𝑋 = 𝑐 ⋅ 𝐄 𝑋 . ◼ By definition, 𝐄 𝑋 = σ𝑥=1 𝑛 𝑥 ⋅ 𝐏𝐫 𝑋 = 𝑥 . ◼ But this seems complicated to compute. 5