Approximation Algorithms and Linear Programming

This course continues our data structures and algorithms specialization by focussing on the use of linear and integer programming formulations for solving algorithmic problems that seek optimal solutions to problems arising from domains such as resource allocation, scheduling, task assignment, and variants of the traveling salesperson problem. Next, we will study algorithms for NP-hard problems whose solutions are guaranteed to be within some approximation factor of the best possible solutions. Such algorithms are often quite efficient and provide useful bounds on the optimal solutions. The le…