Integer Linear Programming

Introduction to Integer Linear Programming (ILP). We are going to take a look at ILPs for three problems: - maximum weight perfect matching - minimum vertex cover - maximum independent set 00:00 Integer Linear Programming 04:13 Maximum Weight Perfect Matching 09:54 Integer solution to the LP relaxation 17:49 Minimum Vertex Cover 19:38 Rounding 24:34 Maximum Independent Set 25:58 LP relaxation not helping