Network Optimization
| Code | 627 |
|---|---|
| Semester | Fall |
| Class Hours - Lab Hours | 3 - 0 |
| Lecturers | Miltiades Anagnostou |
| Links | Course's Website |
| Web Platform |
Class 1:
BigBlueButton
|
Description
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.