Unit 6: Dealing with NP-hard problems using approximation algorithms

Question 1

Coping with NP-completeness

Answer 1

**Sacrifice one of 3 desired features:
**
- Solve problem to optimality (heuristic and approximation algorithms)

• • Solve problem in polynomial time -> algorithms with exponential runtime (e.g. branch-and-bound, parameterized algorithms)
• Solve arbitrary instances of the problem (identify special cases solvable in polynomial time)

Question 2

Graph

Interval graph

Answer 2

A graph G = (V, E) is an interval graph if there is a set I = {I_v ⊂ Q | v ∈ V} of intervals such that:
- G has an edge between u and v if and only if I_u ⋂ I_v ≠ ∅.

Question 3

Knapsack problem

Answer 3

n items with positive integer weights w₁, ... , wₙ and values v₁, ... , vₙ as well as a positive integer capacity C.

Task: Find a subset S of items with weight ≤ C that maximises the total value.

Question 4

Knapsack problem:
Dynamic programming main idea

Answer 4

Main idea
- Order the n items arbitrarity from 1 to n.
- Process the items one by one from 1 to n.
- At the ith step, store information about the best possible solutions that use only the first i items.
- Use the information stored for the first i items to compute the information for the first i+1 items.

The stored information at step i has to be sufficient to:
- Obtain the best solution, i.e. the best possible value of any subset of items that fits into the knapsack, when one is only allowed to use the first i items.
- To compute the information for the first i+1 items given the information for the first i items.

Question 5

Knapsack problem:
Dynamic programming algorithm

Answer 5

Definition: OPT(i, c) = maximal value for the subset 1, ..., i of items assuming a **total capacity of ** c.

Case 1: OPT(i, c) is achieved by a solution that does not contain item i. Then OPT(i, c) = OPT(i - 1, c), since we know that a solution does not contain item i.

Case 2: OPT(i, c) is achieved by a solution that contains item i.
- new (remaining) total capacity = c - wᵢ
- Therefore, `OPT(i, c) = vᵢ + OPT(i - 1, c - wᵢ)

Question 6

Knapsack: Dynamic programming Run-time

Answer 6

O(nC)

• Polynomial in n.
• However, the run-time depends also on the capacity of the knapsack.
  
  • C is exponential in the input length, since numbers are encoded in binary.
  • The run-time is therefore not polynomial in the input size.
• “Psuedo-polynomial”

Question 7

Knapsack improvement:

memorisation

Answer 7

It is not necessary to store the whole array.

Improvement:
- only remember the last row
- updating the entries from left to right.

Question 8

Knapsack: dynamic programming II

Answer 8

Def: OPT(i, v) = min weight subset of items 1, ..., i that yields value exactly v.

Case 1: OPT(i, v) is achieved by a solution not containing i. OPT(i, v) = OPT(i-1, v), since we know that the solution does not contain i.

Case 2: OPT(i, v) is achieved by a solution that contains i.
- consumes weight wᵢ, new value needed = v - vᵢ
- Therefore, OPT(i, v) = wᵢ + OPT(i - 1, v - vᵢ)

Run-time: O(nV*) = O(n² v_max) (because V* ≤ n v_max).
- V* = optimal value = maximum v such that OPT(n, v) ≤ C.
- Not polynomial in input size!