Network Flows and More on Combinatorial Optimization
19 novembro 2024, 14:30 • José Rui De Matos Figueira
The minimum cost network flow problem and its particular cases: shortest paths, maximum flow, circulation problem, transportation and assignment problems. The network primal simplex algorithm, the Dijkstra and Bellman-Ford algorithms for shortest path problems, the Ford-Fulkerson algorithm for the maximum flow problem, the Dantzig algorithm for the transportation problems and the Hugarian agorithm for the assignment problem. The minimum spanning tree problem and the Kruskal algorithm. More on combinatorial optimization: sat problem, set covering, clustering problem, infeasible systems of linear equations. Solving the knapsack problem with dynamic programming and a labeling algorithm.