Basic Concepts of Combinatorial and Network Optimization
Basic models of optimization problems. Representation of optimization problems and their relation to algorithmic efficiency and time complexity.
Advanced Algorithmic Techniques for Solving Fundamental Optimization Problems
Shortest paths: features and properties. Theorems for computing and verifying an optimal solution. Shortest path algorithms (Dijkstra, Bellman-Ford-Moore, Dial, Radix-Heap) and other efficient implementations using priority queues. Methods for detecting and computing negative cycles.
Maximum flow: features and properties. Theorems for computing and verifying an optimal solution. Maximum flow algorithms: augmenting path, shortest augmenting path, preflow-push.
Minimum cost flow: features and properties. Theorems for computing and verifying an optimal solution. Algorithms: negative cycle cancelling, successive shortest path.
Generic Techniques for Solving Optimization Problems
Introduction to generic optimization techniques. Global and local optimum. Convex programming. Linear programming. Basic feasible solutions and the Simplex method. Duality. The Ellipsoid method. Interior-point methods. Integer programming.