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).

Get Higher Grades Now

Tutors Online

Get Free Quote!

332 Experts Online