DAA 30 – Knapsack: Pseudopolynomial DP, PTAS, FPTAS & Approximation Scheme | CS F364

This lecture is DAA 30 in the Design and Analysis of Algorithms (DAA) course (CS F364). It studies the Knapsack problem from the perspective of dynamic programming and approximation schemes, and develops an FPTAS for Knapsack.

The lecture begins with the standard 0/1 Knapsack problem: given items with integer sizes and values, and a knapsack of capacity B, the goal is to choose a subset of items whose total size does not exceed the capacity and whose total value is maximum. A dynamic programming algorithm is then presented using lists of pairs (t, w), where each pair records an achievable total size and total value using the first j items.

A key idea in the algorithm is the removal of dominated pairs. A pair is dominated if another pair achieves at least as much value using no more space. By retaining only nondominated pairs, the algorithm keeps the representation compact while still preserving optimal solutions. This yields a dynamic programming method with running time
O(n min(B, V)), where V is the sum of item values. The lecture explains why this is not polynomial time in the input length, but is instead a pseudopolynomial-time algorithm.

The lecture then introduces the notions of PTAS and FPTAS. After defining these approximation frameworks, it develops an FPTAS for Knapsack by scaling and rounding the item values. A suitable parameter mu is chosen in terms of epsilon and the maximum single-item value lower bound, and each value is replaced by a rounded-down scaled version. The dynamic programming algorithm is then run on the modified values.

The running time of the resulting algorithm is shown to be polynomial in both n and 1 over epsilon, and the lecture proves that the returned solution has value at least
(1 minus epsilon) times OPT. This establishes that the algorithm is indeed an FPTAS for Knapsack.

This lecture is important because it shows how pseudopolynomial dynamic programming can be transformed into a fully polynomial-time approximation scheme, a key idea in approximation algorithms.

📌 Topics Covered in This Lecture

0/1 Knapsack problem

Dynamic programming for Knapsack

Lists of achievable size-value pairs

Dominated and nondominated pairs

Removing dominated pairs

Running time O(n min(B, V))

Pseudopolynomial-time algorithms

Definition of PTAS

Definition of FPTAS

Value scaling and rounding

FPTAS for Knapsack

Approximation guarantee of 1 minus epsilon

Polynomial dependence on 1 over epsilon

🎯 Who Should Watch

Students studying Design and Analysis of Algorithms

B.Tech / BE / M.Sc. / MCA / GATE aspirants

Learners studying approximation algorithms and dynamic programming

Anyone seeking a clear understanding of Knapsack approximation schemes

🔗 Playlist

This video is part of the playlist:
Design and Analysis of Algorithms – Complete DAA Course

Видео DAA 30 – Knapsack: Pseudopolynomial DP, PTAS, FPTAS & Approximation Scheme | CS F364 канала Abhishek Mishra – Mathematics & TCS