An advertising company underwent a thorough reorganization during which the m employees of the department of Creative Designers got laid oﬀ. However n > m new positions have been created in the company. The human resources manager interviews all m employees regarding their interest in the positions and their qualiﬁcations. Then he assigns a score sij to each employee i for each position j (s)he is willing to accept reﬂecting how qualiﬁed employee i is for position j.

The goal of the manager is to assign jobs to employees so that the sum of the scores of the employees who are assigned to jobs is maximized. A single job cannot be assigned to more than one employee and a single employee may not be assigned to more than one job.

i. (4 points) Formulate an integer program (IP) for this problem.

ii. (4 points) Formulate this problem in graph-theoretic terms and explain what the above IP ﬁnds.

iii. (4 points) Now suppose that sij = 1 for every employee i that qualiﬁes for a job j. Explain in graph-theoretic terms what the IP ﬁnds.

iv. Now consider the speciﬁc instance of the above problem where m = 2, n = 3, sij = 1 for all 1 ≤ i ≤ 2,1 ≤ j ≤ 3. i. (12 points) Write out the IP for this instance. Write the LP for its linear programming relaxation and take the dual of the relaxed LP (show all your work). ii. (8 points) Assume that the dual LP has an integral solution. Interpret the dual LP in graph-theoretic terms