Alpha Beta Gamma is starting a college in Delaware (DE), called ayde College (or College A, for short). There are m different courses that that must be taught (one section each). There are n applicants for professorships. Applicant i requires salary s and can teach courses from set Ci. If hired, the applicant must teach any or all of the courses in set Ci as requested by the college during a semester. (The ability to teach many different courses at the same time is good for getting hired, but could be burdensome for the professor during the semester.) Alpha Beta Gamma wants to hire professors at the smallest possible total salary who can cover all of the courses. Obviously, quality is not important. There is a maximum amount of money that Alpha Beta Gamma is willing to spend on salaries. Alpha Beta Gamma does not want to bother finding an optimal solution if there is no way to hire professors within the salary cap. There are two problems that need to be solved. (1) Given m courses (numbered 1,...,m), n applicants (numbered 1,...,n), integers si and sets Ci, such that applicant i will teach any subset of courses in C; for salary si, and salary cap S, determine if there is a way to hire professors to cover all of the courses for total cost at most S. (2) Given m courses (numbered 1,...,m), n applicants (numbered 1,...,n), integers si and sets Ci, such that applicant i will teach any subset of courses in Ci for salary si, find a way to hire professors to cover all of the courses with cheapest total cost. These two problems seem to be hard to solve efficiently. Not surprisingly, your manager asks you to write programs to solve the two problems. As usual, you have no idea how to write such programs. You find efficient programs on the Internet that solve both problems. Unfortunately your budget will only allow you to buy one such program. 15. Assume that you have a program that solves the second problem in time (m+n)). Can you use it to solve the first problem in polynomial time? If so, how, and how fast is your algorithm? 16. Assume that you have a program that solves the first problem in time (m+n)5). Can you use it to solve the second problem in polynomial time? If so, how, and how fast is your algorithm? Things get more complicated: Alpha Beta Gamma decides to open a second college in Maryland (MD) called ayud College (or College B, for short), offering exactly the same courses. A professor may only teach at one college during a semester. Fortunately, professors are willing to move to either location. There are two problems that need to be solved. (3) Given m courses (numbered 1,...,m), n applicants (numbered 1,...,n), integers si and sets Ci, such that applicant i will teach any subset of courses in Ci for salary si, and salary cap S, determine if there is a way to hire professors to cover all of the courses at two colleges for total cost at most S. (4) Given m courses (numbered 1,...,m), n applicants (numbered 1, ..., n), integers si and sets Ci, such that applicant i will teach any subset of courses in C; for salary si, find a way to hire professors to cover all of the courses at two colleges with cheapest total cost. These two problems seem to be hard to solve efficiently. Again, your manager asks you to write programs to solve the two problems. As usual, you have no idea how to write such programs. You find efficient programs on the Internet that solve both problems. Unfortunately your budget will only allow you to buy one such program. 17. Assume that you have a program that solves the second problem in time (m+n)8). Can you use it to solve the first problem in polynomial time? If so, how, and how fast is your algorithm? 18. Assume that you have a program that solves the first problem in time ((m+n)). Can you use it to solve the second problem in polynomial time? If so, how, and how fast is your algorithm? Alpha Beta Gamma is starting a college in Delaware (DE), called ayde College (or College A, for short). There are m different courses that that must be taught (one section each). There are n applicants for professorships. Applicant i requires salary s and can teach courses from set Ci. If hired, the applicant must teach any or all of the courses in set Ci as requested by the college during a semester. (The ability to teach many different courses at the same time is good for getting hired, but could be burdensome for the professor during the semester.) Alpha Beta Gamma wants to hire professors at the smallest possible total salary who can cover all of the courses. Obviously, quality is not important. There is a maximum amount of money that Alpha Beta Gamma is willing to spend on salaries. Alpha Beta Gamma does not want to bother finding an optimal solution if there is no way to hire professors within the salary cap. There are two problems that need to be solved. (1) Given m courses (numbered 1,...,m), n applicants (numbered 1,...,n), integers si and sets Ci, such that applicant i will teach any subset of courses in C; for salary si, and salary cap S, determine if there is a way to hire professors to cover all of the courses for total cost at most S. (2) Given m courses (numbered 1,...,m), n applicants (numbered 1,...,n), integers si and sets Ci, such that applicant i will teach any subset of courses in Ci for salary si, find a way to hire professors to cover all of the courses with cheapest total cost. These two problems seem to be hard to solve efficiently. Not surprisingly, your manager asks you to write programs to solve the two problems. As usual, you have no idea how to write such programs. You find efficient programs on the Internet that solve both problems. Unfortunately your budget will only allow you to buy one such program. 15. Assume that you have a program that solves the second problem in time (m+n)). Can you use it to solve the first problem in polynomial time? If so, how, and how fast is your algorithm? 16. Assume that you have a program that solves the first problem in time (m+n)5). Can you use it to solve the second problem in polynomial time? If so, how, and how fast is your algorithm? Things get more complicated: Alpha Beta Gamma decides to open a second college in Maryland (MD) called ayud College (or College B, for short), offering exactly the same courses. A professor may only teach at one college during a semester. Fortunately, professors are willing to move to either location. There are two problems that need to be solved. (3) Given m courses (numbered 1,...,m), n applicants (numbered 1,...,n), integers si and sets Ci, such that applicant i will teach any subset of courses in Ci for salary si, and salary cap S, determine if there is a way to hire professors to cover all of the courses at two colleges for total cost at most S. (4) Given m courses (numbered 1,...,m), n applicants (numbered 1, ..., n), integers si and sets Ci, such that applicant i will teach any subset of courses in C; for salary si, find a way to hire professors to cover all of the courses at two colleges with cheapest total cost. These two problems seem to be hard to solve efficiently. Again, your manager asks you to write programs to solve the two problems. As usual, you have no idea how to write such programs. You find efficient programs on the Internet that solve both problems. Unfortunately your budget will only allow you to buy one such program. 17. Assume that you have a program that solves the second problem in time (m+n)8). Can you use it to solve the first problem in polynomial time? If so, how, and how fast is your algorithm? 18. Assume that you have a program that solves the first problem in time ((m+n)). Can you use it to solve the second problem in polynomial time? If so, how, and how fast is your algorithm
