Network Optimization

Code 627
Semester Fall
Class Hours - Lab Hours 3 - 0
Lecturers Miltiades Anagnostou
Links Course's Website
Web Platform Class 1: BigBlueButton


Introduction to graph theory for networks. Network Flow Problems, flow composition. Minimum cost flow, multicommodity flows, network flow algorithms. Discrete network optimization problems. Shortest path problems, label setting/correcting, auctions. Maximum flow, minimum cut, Ford-Fulkerson algorithm, price-based algorithms. Minimum Cost Flow Problems, dual problem, Simplex. Problems with integral constraints, Lagrange relaxation. Approximation algorithms for NP-hard problems, performance bounds, scheduling examples. Travelling salesman, Steiner tree. Geometric problems. Online algorithms. Monte Carlo methods. Taboo search, genetic algorithms, simulated annealing.