Algorithms and Combinational Optimization

Course Code: 
CEID_NE5057
Period: 
Winter Semester
Instructors: 
Credit Points: 
5

Course outline 

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.

Startup Growth Lite is a free theme, contributed to the Drupal Community by More than Themes.