QUESTION 1. Construction: 12pts Proof of correctness: 3pts Many students got this question wrong. First we should focus on the problem of deciding if such an assignment exists. This in fact makes the problem simpler. Next we observe that there exists an assignment, in which we hire at least d candidates from each group, if and only if there exists an assignment, in which we hire *exactly* d candidates from each group. Thus, it suffices to construct a flow network to decide the relax problem where we need to hire *exactly* d candidates from each group. It should be easier to construct a flow network for the relax problem. ========================== A possible solution is the following flow network: - Source s, sink t, vertices G_1,...,G_k to represent k groups, vertices c_1,...,c_n to represent n candidates, and vertices p_1,...,p_m to represent m positions. - Edges from s to each g_i with capacity d; edges from each G_i to every candidate c_j who belongs to G_i with capacity 1; edges from each candidate c_j to every position p_l in the set C_j with capacity 1; edges from each position p_l to t with capacity 1. Using this network, we can use the network flow to decide the problem as follows. We find a max-flow f of this network, and if for all i in {1,...,k}, f(s,g_i)=d, then we output YES (i.e. such an assignment exists). Otherwise, we output NO. ========================== In the proof of correctness, we need to show two statements: - If we have an assignment to the original problem (where "at least" d candidates in each group are hired), then we can construct a flow f for the network such that for all i in {1,...,k}, f(s,g_i)=d. - Conversely, if a flow f for the network such that for all i in {1,...,k}, f(s,g_i)=d, then we can construct an assignment to the original problem where "at least" d candidates from each group are hired (we actually hire exactly d candidates from each group, but this is sufficient). It is very important to note that an assignment produced by a maximum flow might be *smaller* than a maximum assignment, since we force that f(s,g_i)<=d for all i. This is different from A3, where the assignment produced by a maximum flow is always a maximum assignment for the original problem. If your proof missed one of these two statements or if it's not clear what you're trying to prove, I took away 1-3pts. ========================== Another valid solution is to use a network flow with maximum and minimum flow constraints (as discussed in Tutorial #5) to require that all edges (s,g_i) in the above flow network have capacity at least d. Only 3 students tried this approach even though it seems more natural. ========================== Unfortunately, other approaches that students tried didn't work. If this is the case, you give up to 6/15 marks for a good attempt. QUESTION 2. Construction: 12pts Proof of correctness: 3pts Most students did well on this question. A possible LP solution is: Objective: minimize d_1+d_2+...+d_n Subject to: b_i<=b_{i+1} for i=1,...,n-1 a_i-b_i<=d_i for i=1,...,n b_i-a_i<=d_i for i=1,...,n ========================== Notes: * We always have a_i-b_i>=0 or b_i-a_i>=0, so constraints d_i>=0 are redundant. * The function d_1+d_2+...+d_n is already linear, so there's no need to add a variable d, a constraint d_1+d_2+...+d_n <= d, and then minimize d. I didn't take away any mark for these redundancies. ========================== I took away 1pt, if you use the constraint b_1<=b_2<=...<=b_n (which is not yet in the proper form for a linear constraint) instead of b_i<=b_{i+1} for i=1,...,n-1. Another common mistake is to forget arguing that each solution b_1,...,b_n to the problem corresponds to an LP solution with objective value exactly deviation(b_1,...,b_n). This is very similar to the mistake that students made in Q2 of A3; unfortunately many students repeated the same mistake again. For this, I only took away 1pt. But this is a very serious mistake. If your solution looks nothing like an LP, you get 0/15.