1.  (40 points) Suppose that you want to hire specialists to perform a set of tasks T, but only have a budget of b dollars.  After looking around, you have found n  candidates.  Each candidate i ∈ {1,..., n} has a salary W[i] that they demand and can only perform a subset S[i] ⊆ T of the required tasks.  The goal is to determine whether it is possible to hire a subset of the candidates so that they can collectively perform all the required tasks while keeping within budget. More formally, this budgeted hiring problem is specified as follows:

. Input:  (b,T, W[1..n], S[1..n]), where b is a positive integer, T is a set, W[1..n] is an array of positive 32-bit integers, and S[1..n] is an array of subsets of T.

.  Output: yes, if there exists a set of indices I ⊆ {1,..., n} such that ni=IS[i] = T and Σi=IW[i] ≤ b; no, otherwise.

.  sizeof(b,T, W[1..n], S[1..n]) = O(logb + n|T|).

For example, if the set of required tasks is T = {cleaning, sales, stocking} and there are 4 candidates who demand salaries W = [50, 90, 80, 30] and can perform tasks

S = [{cleaning, sales}, {sales, stocking}, {stocking}, {cleaning, sales}] ,

respectively, then (120,T,W, S) is a “yes” input, while (109,T,W, S) is a “no” input.

(a)  Show that the budgeted hiring problem is in NP by specifying averifier for the problem. Remember to prove the correctness and analyze the running time of your verifier.

(b)  Show that the vertex cover problem is polynomial-time mapping reducible to the bud- geted hiring problem. Remember to prove the correctness and analyze the running time of your mapping reduction.  Hint:  Each vertex should be a candidate.

(c) Is it reasonable to ask you to give a polynomial-time algorithm for the budgeted hiring problem during a coding interview or on the job? Explain why or why not.

2.  (20 points) The budgeted hiring problem can be viewed as the decision variant of a  (more natural) search problem: to find (and hire) a subset of the candidates who can collectively per- form all the required tasks while minimizing their total salary. More formally, the minimum salary hiring problem is specified as follows:

• Input:   (T, W[1..n], S[1..n]), where T is a set,  W[1..n] is an array of positive 32-bit integers, and S[1..n] is an array of subsets of T.

•  Output: a set of indices I ⊆ {1,..., n} such that ni=IS[i] = T andΣi=IW[i] is mini- mized (among all sets of indices J ⊆ {1,..., n} such that nj=JS[j] = T), or “impossible” if no such set of indices exists

•  sizeof(T, W[1..n], S[1..n]) = O(n|T|).

For example, if the set of required tasks is T = {cleaning, sales, stocking} and there are 4 candidates who demand salaries W = [50, 90, 80, 30] and can perform tasks

S = [{cleaning, sales}, {sales, stocking}, {stocking}, {cleaning, sales}] ,

respectively, then the output for input (T,W, S) should be {3, 4}, that is, you should hire candidates 3 and 4, so that their total salary is $110.

Show that the minimum salary hiring problem efficiently reduces to the budgeted hiring problem.  In particular, assume that you have an oracle for the budgeted hiring problem, called BudgetHire, and show that it is possible to solve the minimum salary hiring problem by using a polynomial number of calls to BudgetHire (along with some extra polynomial- time computation). Remember to prove the correctness and analyze the running time of your (search-to-decision) reduction.

Hint:  First determine the minimum total salary possible.  Then think about how to  remove certain people from consideration...

3.  (20 points) A  “realistic”  restriction of the minimum salary hiring problem might be that (i) each candidate demands a salary between  s1000  and  s2000  and  (ii)  each  task  has  at most 3 candidates who are capable of performing that task, i.e., for each i ∈ {1,..., n}, 1000 ≤ W[i] ≤ 2000 and for each t ∈ T, |{j ∈ {1,..., n} | t ∈ S[j]}| ≤ 3.  The goal of this question is to show that, under these restrictions, the following approximation algorithm for hiring candidates is actually pretty good:

For example, suppose that the set of required tasks is T = {cleaning, sales, stocking} and there are 4 candidates who demand salaries W =  [1500, 1900, 1800, 1300] and can perform tasks

S = [{cleaning, sales}, {sales, stocking}, {stocking}, {cleaning, sales}] ,

respectively. In the first iteration of the loop, we can choose any task in T on line 5.  Suppose we choose t1  = stocking.  Then we compute the set of candidates A1  = {2, 3} who can perform t1 online 5, and update I = {2, 3} online 7.  Since ni∈IS[i] = S[2]∪S[3] = {sales, stocking}, in the next iteration, the only task we can choose on line 5 is t2  = cleaning.   The set of candidates who can perform t2  is A2  = {1, 4}, so we update I = {1, 2, 3, 4}.  At this point, ni∈IS[i] = S[1] ∪ S[2] ∪ S[3] ∪ S[4] = T and {1, 2, 3, 4} is returned.

Fix an input (T, W[1..n], S[1..n]) to the algorithm that satisfies the restrictions stated above and assume that n S[i]  = T (so that the algorithm returns a set of candidates).   Let t1 , t2 ,..., tk  be the sequence of tasks chosen on line 5 of the algorithm, let A1,...,Ak  be the corresponding sets of candidates computed on 6 of the algorithm, and let I = A1∪A2∪···∪Ak be the set of candidates returned by the algorithm. Prove each of the following claims.

(a) For any two tasks ti    tj  chosen by the algorithm, the set of all candidates that can perform the respective tasks are disjoint,i.e., Ai∩Aj  = ∅ .  Hint:  Show that A1 ∪···∪Ak is disjoint from Ak+1 .

(b) For any set I′  ⊆ {1,..., n} of candidates that can collectively perform all tasks in T, the total salary of the candidates in I′  is at least  1000k, i.e., if ni′ ∈I′  S[i] = T, then Σi′ ∈I′  W[i′] ≥ 1000k. Hint:  Using (a), argue why |I′| ≥ k.

(c)  The total salary of the candidates in I is at most 6 times the total salary of any  set of candidates I′ that can collectively perform all tasks in T, i.e., Σi∈IW[i] ≤ 6 Σi′ ∈I′  W[i′]. In other words, the algorithm achieves a 6-approximation.   Hint:   How  large  can  |I| be with respect to k given the restrictions?   Also, what is the maximum salary of a candidate?

4.  (20 points) In this question, we explore a randomized  approximation algorithm for the mini- mum salary hiring problem, which does not require any restrictions on the input.  Given an instance with n candidates, say (T, W[1..n], S[1..n]), the idea is to view a proposed solution (a set of candidates to hire) as a vector (x1 , x2 ,..., xn), which should satisfy two constraints:

(1)  For each i ∈ {1,..., n}, xi  is either 0 or 1.  (Each  candidate i is  either hired or not hired; xi = 1 means yes, xi = 0 means  no.)

(2) For each task t ∈ T, if A(t) = {j ∈ {1,..., n} | t ∈ S[j]} is the set of all candidates who can perform the task t, then：j∈A(t)xj  ≥ 1.  (For  each  task,  we  must hire  at  least one candidate who  can perform the  task.)

The minimum salary problem is then equivalent to finding  a vector  (x1 , x2 ,..., xn) that satisfies constraints (1) and (2), while minimizing： W[i] · xi, the total salary.

This is an example of an  integer programming  problem,  for  which  are no known efficient

algorithms. However, it turns out that, if we relax constraint (1) to:

(1’)  For each i ∈ {1,..., n}, xi  is a real number between 0 and 1.

then it is possible to efficiently solve the resulting linear programming  problem, i.e., find a vector (x1 , x2 ,..., xn) that satisfies constraints (1’) and (2),while minimizing： W[i] · xi. In the following, assume that we have computed such a vector (x1 , x2 ,..., xn).

(a) Let (x1(′), x2(′),..., xn(′)) bean optimal solution to the minimum salary problem when viewed as a vector, i.e., (x1(′), x2(′),..., xn(′)) satisfies constraints (1) and (2) and： W[i] · xi(′)  is minimal. Explain why： W[i] · xi  ≤： W[i] · xi(′) .

(b)  Consider the following random experiment: independently, for each i ∈ {1,..., n}, hire candidate i with probability xi  (and do nothing with probability 1 − xi).

i. What is the expected total salary of the hired candidates?  Justify your answer by setting up the appropriate random variables and applying linearity of expectation.

ii. Let t ∈ T be any fixed task.  Show that the probability that we do not hire any candidate who can perform the task t is at most 1/e, where e ≈ 2.718 is Euler’s number.  Hint:   Constraint (2) is key.  You may use, without proof, the fact that 1 − x ≤ e−x  for any real number x.

(c)  Suppose  we perform ln(k|T|) independent trials of the  above experiment,  so  that  a candidate gets hired if they are hired in any trial.

i. Let t  ∈ T be any fixed task.   What is the probability that we did not hire any candidate who can perform the task t?  (You may use the results in part  (b), even if you did not prove them.)

ii.  Show that the probability that there is some  task for which we did not hire any candidate who can perform the task is at most 1/k.  Hint:  Apply the union bound Pr(A or B) ≤ Pr(A) + Pr(B).

iii.  5 bonus points: Explain why this algorithm achieves an O(log |T|)-approximation of the minimum salary hiring problem with probability 1 − O(1/k).

Fun fact: if you can find an ((1 − o(1))ln|T|)-approximation for the minimum salary hiring problem, then this would imply that P = NP!  The moral is that some problems might even be difficult to efficiently approximate  (beyond a certain ratio).