CSC 341 (Fall 2021)

Reading: Approximation with Linear Programming

In today’s class, we’ll look at the connections between linear programming, a problem known to be in \(P\), integer linear programming, a specialization of linear programming known to be \(\mathsf{NP}\)-hard, and how we can exploit this connection in creating approximation algorithms.

If you have seen linear programming before in a previous class, feel free to review those materials to refresh your memory. For those of you that are new to linear programming, read this brief article on brilliant.org about the subject:

Read the first half of the article in detail to understand what the linear programming is about. You can skim the section on the Simplex method which is the canonical “first” method for solving linear programs.