Interviewing Secretaries in Parallel
Explore the classical secretary problem, algorithmic solutions, related works, and our model for optimizing hiring decisions. Discover insights into hiring the best secretaries efficiently. Uncover the competitive ratio and the implications of various secretary problem variants. Dive into the world of algorithms, LPs, and the quest to hire the top candidates with high probability. Learn about parallel interviewing strategies and the unique challenges faced in selecting the best candidates from a pool of applicants.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Interviewing Secretaries in Parallel Moran Feldman Moshe Tennenholtz
Outline The classical secretary problem Related works Our model Evaluating algorithms - The competitive ratio Results 2
The Secretary Problem n secretaries: strictly ordered by quality. The Secretaries are interviewed one after the other, in a random order. In the interview: The quality of the secretary relative to the previously seen secretaries is revealed. We can hire the secretary, or dismiss her. In both cases, the decision is final. Goal: Hire the best secretary with high probability. Question: How good can we do? We can succeed with probability 1/e! [Libdley61, Dynkin 1963] 3
The Algorithm Algorithm 1. Inspect the first n/e secretaries; let s be the best secretary among these. 2. Interview the rest of the secretaries; hire the first one better than s (better than any previously seen secretary). It can be shown that this algorithm succeeds with probability at least 1/e. [Libdley61, Dynkin63] 4
Related Works Many variants of the secretary problem were considered. Hire up to k secretaries with maximum total value. [Kleinberg 2005] Secretaries lose value over time. [Babaioff et al. 2009] A somewhat inferior early secretary is better than a better late secretary. The set of secretaries has a partial order. [Georgiou et al. 2008, Kumar et al. 2011] Some pairs of secretaries cannot be compared. 5
Related Works - Tools Algorithms Capturing LPs Family [Buchbinder et al. 2010] Each LP captures all algorithms for a given variant of the secretary problem for n secretaries. An optimal solution for the LP induces an optimal algorithm for a given n, and vice versa. Dual solutions provide hardness results (some of our hardness results use this technique). An alternative arrival process. [Feldman et al. 2011] Random arrival times for the secretaries instead of random arrival order. More on this later. 6
Our Model Enough time to interview only D secretaries. To speed up: secretaries split into Q queues. Each queue gets Q / n secretaries. Allows D Q secretaries to be interviewed. We want to hire the top k secretaries. Each queue has an independent interviewer. Required to allow parallelism of interviews. Secretaries from different queues cannot be compared. D 7
Sub-Model 1 - Exclusive Positions Motivation: door-to-door sellers Most clients require minimal time: not at home, not interested, etc. Clients that are likely to buy the product require a much longer visit. Each evening, the seller interviews clients till he finds a serious client to hire . Back to the model: Here, each interviewer has a single position to man. In general, each interviewer has a subset of the k positions which only he can man. 8
Sub-Model 2 Shared Positions Motivation: security checks at an airport The passengers split into queues. Most passengers are allowed to pass after a short interview. Some passengers are escorted to farther investigation by senior personal. The senior personal are the position which can be manned from every one of the queues. Back to the model: Every position can be manned from each queue (but at most once). 9
Competitive Ratio How do we evaluate an algorithm for this model? Notation ALG(n) The number of top k secretaries hired by ALG on an input of n secretaries. Notice that ALG(n) is a random variable of: The arrival order. The randomness of ALG itself. Competitive Ratio Definition: ( ) n E ALG k Remark: This is not exactly the standard definition of competitive ratio. 10
Hiring 2 Secretaries from 2 Queues Formally: k = 2, Q = 2, D = n / 2 Toy example. Demonstrates: Counter intuitive results Techniques Consider 3 subcases: Exclusive Positions Shared Positions One Queue: there is only one queue, from which we interview n / 2 secretaries. 11
The Arrival Process The Arrival Process Secretaries arrive in a random order (random permutation). Alternative Arrival Process [Feldman et al. 2011] Secretaries arrive at random times within the range [0, 1]. Equivalence of the Arrival Processes for Single Queues Random arrival times induce a random permutation. Choose n random arrival times, sort them, and assign them to the secretaries upon arrival. 1/2 1/3 4/5 12
The Arrival Process (cont.) What about multiple queues? Exclusive positions. The two arrival processes are equivalent. Shared positions. The two arrival processes are not equivalent. Still, an algorithm for one process usually induces an algorithm for the other process with the same competitive ratio up to low order terms. We describe most of our algorithms in terms of the continuous time arrival process. 13
Subcase 1: Exclusive Positions Na ve idea: apply the classical algorithm to each queue separately. Strong evidence that this is only 0.3097-competive. In each queue independently do: Wait till time t. For every secretary s arriving: Hire s if it is better than any previously seen secretary. For t = 1/e we get (almost) the classical secretary algorithm. For t = 0.35: an improved competitive ratio of 0.319. No algorithm can be better than 0.321-competitive. 14
Subcase 1: Exclusive Positions (cont.) Rethinking about the problem. Each queue faces the following problem. From the set of secretaries arriving (to the queue), hire one. So why the classical algorithm was not optimal? If the queue gets exactly one of the top 2 secretaries, choosing t = 1/e is optimal. If the queue gets both top 2 secretaries, a smaller value of t is optimal. The value t = 0.35 is a middle point between these two values. 15
Summary Table Subcase Exclusive Positions Shared Positions Single Queue Approximation Hardness 0.319 0.321 16
Subcase 2: Shared Positions Algorithm: Wait till time t1 = 0.348. While no secretary was hired, for every secretary s arriving: Hire s if it is better than any previously seen secretary. Wait till time t2 = 0.563 (if it was not reached yet). While there is still a position to man, for every secretary s arriving: Hire s if it is better than any previously seen secretary. Competitive ratio: 0.356 Intuition: When we have two available positions, it is more important to man them both than to avoid mistakes. The opposite is true when we are left with only one available position. t1 t2 17
Summary Table Subcase Exclusive Positions Shared Positions Single Queue Approximation Hardness 0.319 0.321 0.356 - 18
Subcase 3: Single Queue Comparison with Exclusive Positions . Can interview only half the secretaries. More freedom in hiring secretaries. Hardness: 0.266 - weaker model than Exclusive Positions . Algorithm: Wait till time t = 1 (1/3)0.5 0.423. Let s be the second best secretary till time t. Hire the first two secretaries better than s. Competitive ratio: 0.192 19
Summary Table Subcase Exclusive Positions Shared Positions Single Queue Approximation Hardness 0.319 0.321 0.356 - 0.192 0.266 20
Other Results One position, d queues and D = n / d for d > 1: Competitive ratio: d-d/(1-d) o(1) (1/d for large d) Tight up to low order terms. Algorithm: all queues wait till time d-1/(1-d), and then the first queue observing a secretary better than all previous, hire her. k positions, 2 queues and D = n / 2: Competitive ratio: 1 o(1) Obviously tight up to low order terms. 21
Other Results (cont.) k positions, k queues and D = n / k: Competitive ratio: 0.288 Hardness: 0.301 (exclusive positions), 0.816 (shared positions) Results also for the single queue variants of the above settings. 22
