Network Optimization I

Course Number: 47835

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: 2023-2024
Semester(s): Mini 1
Required/Elective: Elective
Units: 6

Format

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

Learning Objectives

Upon completing the course, the students should be able to recognize network optimization problems when they arise in applications, and model network problems arising in application areas and identify the techniques that are useful to solve them effectively. They should be able to formulate network optimization problems, develop mathematical programming relaxations, and design efficient algorithms for solving them exactly or approximately.