DISCRETE OPTIMIZATION

Credit Hours: 3 · Undergraduate Upper-Level

Discrete optimization broadly involves finding the best solution from a finite set of possibilities in a computationally efficient manner. Subfields like combinatorial optimization and integer programming are especially popular in industry applications, such as routing deliveries for e-commerce platforms and scheduling virtual machines for cloud companies. In this course, we will explore common discrete problems encountered in practical applications, such as minimum spanning trees, max/min flows, maximum matchings, and scheduling problems. We will analyze the discrete structures underlying these problems and develop algorithms for finding optimal or near-optimal solutions. We will also introduce linear and integer programming to tackle discrete problems. The course will also cover computational complexity and the approximation of several hard problems. Recommended Prerequisite(s): A linear algebra course and COMP 140