Description

Task specification

Provide an answer to the following problem. You may consider any of the material that was presented in the lectures as known.

Problem 1

Necessary definitions

Consider the following measure of comparison between two algorithms A and B, based on their running time and approximation ratio:

• Better running time: Algorithm A has a better running time than algorithm B if A is polynomial time and B is pseudo-polynomial time or exponential time, or if A is pseudo-polynomial time and B is exponential time.

• Better performance: Algorithm A has a better performance than algorithm B if A has a smaller approximation ratio than B.

Remark: The comparisons above are based on the best possible analysis for the algorithms. For instance, a poly- nomial time algorithm is better than a pseudopolynomial time algorithm, only if the latter can not be proven to run in polynomial time. As a concrete example (from the lectures), you can either solve the max flow problem using the Edmonds-Karp algorithm, or using a polynomial-time algorithm for linear programming. If you use the Ford- Fulkerson analysis for Edmonds-Karp (which will give you a pseudopolynomial running time), it would be incorrect to claim that the LP-based algorithm is better than Edmonds-Karp, because the latter actually runs in polynomial time with a better analysis (and they both solve the problem exactly). Similarly, if you prove an approximation ratio α for a polynomial-time algorithm A and an approximation ratio β for a polynomial-time algorithm B, you can safely claim that A is better than B only if α < β and you can not getter a better approximation ratio β′ for B with a better analysis.

An algorithm A that has better running time and better performance than an algorithm B is better than B. An algo- rithm A is best, if there is no other algorithm that is better than it (assuming P ̸= NP).

From the definitions, it follows a polynomial-time algorithm that solves a problem P exactly is obviously best, but if the problem P is NP-hard, then a polynomial-time algorithm with the best possible approximation ratio α > 1 is best, or a pseudopolynomial algorithm that solves it exactly (if it exists) is best. For example, for the 0/1-Knapsack problem, the pseudopolynomial algorithm based on dynamic programming is best, the FPTAS approximation algorithm is best, but the 2-approximation Greedy algorithm is not best, because there is an approximation algorithm which runs in polynomial time and achieves a better approximation ratio (the FPTAS).

The problem

Consider the following problem. A university lecturer aims to schedule a series of 1-hour Q&A sessions with n stu- dents (these are sessions for groups of students, not 1-on-1 meetings) and has set up a doodle poll where there are m available time slots. Every student has indicated which slots they could attend and it turns out that any student appears in at least 1 and at most k time slots in the doodle poll. The lecturer would like to minimise the number of sessions that they will have to do, making sure that they do at least one session for every student (i.e., every student will have a chance to attend some session).