MATH 340 - Discrete Optimization

Semester Offered: Fall
1 unit(s)

(Same as CMPU 340) This course gives a theoretical treatment of fundamental problems in algorithmic graph theory and discrete / combinatorial optimization that lie at the interface of computer science, discrete mathematics, and operations research. We begin with sophisticated and efficient exact algorithms for flow, matching, and cut problems. Next, we tackle NP-hard problems arising in scheduling, clustering, and network design, and explore effective solution approaches through the study of approximation algorithms. Finally, we introduce modern approaches and models, such as decision-making under uncertainty (online algorithms), parameterized analysis, randomized algorithms, and the exploding area of beyond-worst-case analysis. Throughout, we emphasize the power of techniques from continuous optimization, mainly linear programs (LPs), in solving discrete problems, e.g., by introducing frameworks such as LP rounding and the primal-dual method. Heather Newman.

Prerequisite(s): At least one of CMPU 241, MATH 263, AND at least one of CMPU 240, MATH 241, MATH 261 or permission of the department.

Strongly recommend: MATH 221 .

Helpful but not required: MATH 241 .

Two 75-minute periods.

Course Format: CLS