Linear and Discrete Optimization

Catalog description

This course will serve as an introduction to the theory of linear and discrete optimization, which underlies algorithmic methods with connections to both pure and applied mathematics. We will learn fundamental techniques that solve linear programs and discrete optimization problems in a mathematically rigorous way. The focus of the course will be the interplay between geometry, linear algebra and the resulting duality theory and simplex method. Within this framework, we will learn how to prove that an algorithmic solution to a problem of interest is optimal. Satisfies Theory elective within Computer Science major and minor. Satisfies Mathematics major and minor requirement. Prerequisites & Notes Prerequisites & Notes Math 150, one of CSC 120, CSC 121, CSC 200, or CSC 209, and one of CSC/MAT 220, MAT 230, or MAT 255.