IE532: Course Information

Lecture

Lecture is on Tuesdays and Thursdays, 2:00 pm-3:15pm, 410C1 Engineering Hall.

Textbook and optional references

There is no existing text that perfectly matches the content of IE532. However, the following references contain useful additional details and insights.

• Kleinberg and Tardos, Algorithm Design

• Ahuja, Magnanti, and Orlin, Network Flows

• Lovasz, Pelikan, and Vesztergombi, Discrete Mathematics

• van Lint and Wilson, A Course in Combinatorics

You really won't need these books; we list them just in case you want to consult some other references.

Course requirements and grading

Requirements:

• Attendance.

• Homework exercises. Working through (and, yes, often struggling with at length!) the homework is a crucial part of the learning process and will invariably have a major impact on your understanding of the material. In understanding the problems sets, collaboration with your peers in small groups are allowed, even encouraged, but you must write up your own homework to hand in.

• Project: a final project to be described in class.

Grading

• Homework 50%, final project 50%. These weights are approximate; we reserve the right to change them later.

Prerequisites

The course is introductory at a masters level. An undergradudate course in algorithms is not a prerequisite, only familiarity with basics in linear algebra at the level of MATH415 or MATH 416 and knowledge of basic probability at the level of IE410, MATH461, or ECE534. Exposure to programming language (Python) is required.

Course description

In this course, we study algorithms for combinatorial optimization problems with focus on networked systems. These algorithms solve problems that arise in various practical scenarios, including airline companies scheduling their flights, large companies deciding what and where to stock in their warehouses, delivery companies choosing the routes, Google ranking search results, and Netflix choosing which movies to recommend.

We study general combinatorial problems on graphs, each modeling various practical problems of interest. We focus on general and powerful algorithmic techniques for each problem. We learn proof techniques to give guarantees on the quality of the solution found using these algorithms. We apply those algorithms in stylized examples.

Topics

• Cycles and Trees

• Network Flow

• Matching Problems

• Spectral Methods

• Linear Programming

• Online Algorithms

In the second part of this course, we learn deep neural networks and apply them to solve problems on graphs. These are called graph neural networks. The project consists of choosing a graph problem of your interest (perhaps from those we learned in class) and apply graph neural networks to design and train new algorithms that solve the problem.

Course objective

I hope you will enjoy the beauty of algorithms on graphs and networks discussed in this course.