Carnegie Mellon University

Network Optimization II

Course Number: 47836

Network Optimization 1 & 2 (47-835 & 836) are a pair of doctoral level classes that cover basic topics in the intersection of graph algorithms and mathematical optimization. Topics covered include packing and covering problems in graphs such as flows, cuts, and matchings, as well as graph connectivity problems. The courses will demonstrate important tools used in these areas such as total unimodularity, the primal-dual and iterative methods, spectral graph techniques and matroids, and discuss research directions in network optimization. It is appropriate for students enrolled in the ACO program as well as those interested in research in graph theory, combinatorial optimization, and approximation algorithms.


Degree: PhD
Concentration: Operations Research
Academic Year: 2022-2023
Semester(s): Mini 2
Required/Elective: Elective
Units: 6


Lecture: 100min/wk and Recitation: 50min/wk

Learning Objectives

Upon completing the course, the students should be able to recognize network optimization problems and will know the latest techniques to approach this class of problems. Students will be able to formulate network optimization problems, develop mathematical programming relaxations, and design efficient algorithms for solving them exactly or approximately.