Online Algorithm The Secretary Problem
Presented by:
TigerHATS
www.tigerhats.org
Monzur Morshed
TigerHATS - Information is power
The International Research group dedicated to Theories, Simulation and Modeling, New Approaches, Applications, Experiences, Development, Evaluations, Education, Human, Cultural and Industrial Technology
Online Algorithm
An online algorithm is a strategy . - that can process its input piece-by-piece in a serial fashion - decides what to do based only on past information and with no (or inexact) knowledge about the future.
Online algorithm
An Online algorithm responds to a sequence of service requests, each an associated cost. If an algorithm is given the entire sequence of service requests in advance, it is said to be an offline algorithm. We often employ a competitive analysis to analyze an online algorithm.
Application of Online Algorithm
Resource Allocation
- Scheduling - Memory Management - Routing
Robot Motion Planning
- Exploring an unknown terrain - Finding a destination
Computational Finance
List of Online Algorithms
Secretary problem K-server problem Greedy algorithm Adversary Model Job shop scheduling List update problem Metrical task systems Odds algorithm Paging Problem Real-time computing Ski rental problem Linear search problem Search games Algorithms for calculating variance Bandit problem Ukkonen's algorithm
Methods of Analysis
Competitive Analysis (Worst Case)
For any input, the cost of online algorithm is
never worse than c times the cost of the optimal offline algorithm.
Pros: can make very robust statements about the performance of a strategy. Cons: results tend to be pessimistic.
Methods of Analysis
Probabilistic Analysis
Assume a distribution generating the input. Find an algorithm which minimizes the
expected cost of the algorithm.
Pros: can incorporate information predicting the future. Cons: can be difficult to determine probability distributions accurately.
Competitive Analysis
if knew whole input in advance, easy to optimize
C MIN ( )
compare to full knowledge optimum
k-competitive if for all sequences :
The Secretary Problem
The secretary problem is one of many names for a famous problem of the optimal stopping theory. The problem has been studied extensively in the fields of applied probability, statistics, and decision theory. It is also known as the marriage problem, the sultan's dowry problem, the fussy suitor problem, the googol game, and the best choice problem.
The Classical Secretary Problem (CSP)
Rules of the game: There is a single secretarial position to fill. There are n applicants for the position, n is known. The applicants can be ranked from best to worst with no ties. The applicants are interviewed sequentially in a random order, with each order being equally likely. After each interview, the applicant is accepted or rejected. The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far. Rejected applicants cannot be recalled. The object is to select the best applicant. Win: If you select the best applicant. Lose: otherwise Note: An applicant should be accepted only if it is relatively best among those already observed
CSP Solution Framework
A relatively best applicant is called a candidate Reward Function yj(x1,,xn) = j/n if applicant j is a candidate, = 0 otherwise Lets say the interviewer rejects the first r-1 applicants and then accept the next relatively best applicant. We wish to find the optimal r
The Secretary Algorithm
Algorithm:
Observe first n/e elements. Let v=maximum. Pick the next element whose value is > v.
Theorem: Pr(picking max elt. of S) > 1/e.* Proof: Select best elt. if ith best elt is best in first 1/e elts and best elt is first among best (i-1) elts.
2nd best through (i-1)st best ith best best Threshold time t = n/e time t = n
Happens with probability (1/e) (1-1/e)i (1/i).
* Elements come in a random order.
Generalized Secretary Problems
Input Set of secretaries {1, , n}, each has a value vi Feasible or independent family of subsets of {1, , n} Secretaries arrive in random order, and alg. must decide online whether to select each secretary Goal is to select maximum weight feasible set
Performance measure is competitive ratio: E[weight of selected set]/[weight of max ind. set]
The optimal strategy is appealingly simple: Interview the first applicants without making any hiring decisions, then hire the next applicant whose quality exceeds the best of the first m. If you reach the end of the sequence without hiring anyone, then hire the last applicant no matter what.
CSP Solution Framework Cont.
Probability that the best applicant is selected is n Pr = P ( k th applicant is best and selected) k =r
n = P ( k th applicant is best) P ( k th applicant is selected | it is best) k =r n 1 = P ( best of first k - 1 appears before stage r ) k =r n n 1 r 1 r 1 n 1 = = n k = r k 1 k = r n k 1
** (r-1)/(r-1) = 1 if r = 1
CSP Solution Framework Cont.
For optimal r,
Pr +1 Pr r n 1 r 1 n 1 n r +1 k 1 n r k 1
r +1 n
1 1 k 1
r* = min{r 1 :
n r* P 1 1 2 1 3 2 4 2 5 3
1 1} r +1 k 1
6 3 7 3 8 4 9 4
1.000 0.500
0.500 0.458 0.433 0.428
0.414 0.410 0.406
CSP for large n
If n is large, 1 n k 1 log( r ) r +1 log (n/r*) = 1 r* = n / e Pr* = e = 0.368
1 n
Thank you
