Week 8 · Subsets and integer programming

Dynamic programming over subsets is illustrated by Set Cover and Steiner Tree; integer programming appears in allocation, lobbying and imbalance problems.

Lectures

• Dynamic Programming Over Subsets for Set Cover

• Dynamic Programming Over Subsets for Steiner Tree

• ILP for Envy-Free Allocations and Lobbying

• ILP for Imbalance Parameterized by Vertex Cover

Official NPTEL lecture index