20410423 - IN440 - COMBINATORIAL OPTIMISATION

Acquire skills on key solution techniques for combinatorial optimization problems; improve the skills on graph theory; acquire advanced technical skills for designing, analyzing and implementing algorithms aimed to solve optimization problems on graphs, trees and flow networks.

BONIFACI VINCENZO

teacher profile | teaching materials

Fruizione: 20410626 IN440 - OTTIMIZZAZIONE COMBINATORIA in Scienze Computazionali LM-40 BONIFACI VINCENZO

Programme

1. Optimization and combinatorial optimization problems. Enumeration of solutions.
2. Basics of algorithm analysis. Computational tractability. Asymptotic order of growth.
3. Graphs. Graph connectivity and graph traversal. Graph bipartiteness. Connectivity in directed graphs. Directed acyclic graphs and topological ordering.
4. Greedy algorithms. Interval scheduling. Optimal caching. Shortest paths in a graph. Minimum spanning trees.
5. Divide and conquer. Mergesort. Counting inversions. Closest pair of points.
6. Dynamic programming. Weighted interval scheduling. Principles of dynamic programming. Subset sums and knapsacks. All-pairs shortest paths. Shortest paths and distance vector protocols.
7. Network flow. Maximum flow and the Ford-Fulkerson algorithm. Maximum flows and minimum cuts in a network. Augmenting paths. Bipartite matching. Disjoint paths in directed and undirected graphs.
8. Computational intractability. Polynomial-time reductions. Reductions via "gadgets". Efficient certification and the definition of NP. NP-complete problems. Covering, packing, partitioning, sequencing, and numerical problems. Other examples.


Core Documentation

Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson Education, 2013.


Type of delivery of the course

Frontal lectures with recitations and lab. For the class' diary see the teacher's webpage: http://ricerca.mat.uniroma3.it/users/vbonifaci/in440.html

Type of evaluation

Oral exam.

BONIFACI VINCENZO

teacher profile | teaching materials

Fruizione: 20410626 IN440 - OTTIMIZZAZIONE COMBINATORIA in Scienze Computazionali LM-40 BONIFACI VINCENZO

Programme

1. Optimization and combinatorial optimization problems. Enumeration of solutions.
2. Basics of algorithm analysis. Computational tractability. Asymptotic order of growth.
3. Graphs. Graph connectivity and graph traversal. Graph bipartiteness. Connectivity in directed graphs. Directed acyclic graphs and topological ordering.
4. Greedy algorithms. Interval scheduling. Optimal caching. Shortest paths in a graph. Minimum spanning trees.
5. Divide and conquer. Mergesort. Counting inversions. Closest pair of points.
6. Dynamic programming. Weighted interval scheduling. Principles of dynamic programming. Subset sums and knapsacks. All-pairs shortest paths. Shortest paths and distance vector protocols.
7. Network flow. Maximum flow and the Ford-Fulkerson algorithm. Maximum flows and minimum cuts in a network. Augmenting paths. Bipartite matching. Disjoint paths in directed and undirected graphs.
8. Computational intractability. Polynomial-time reductions. Reductions via "gadgets". Efficient certification and the definition of NP. NP-complete problems. Covering, packing, partitioning, sequencing, and numerical problems. Other examples.


Core Documentation

Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson Education, 2013.


Type of delivery of the course

Frontal lectures with recitations and lab. For the class' diary see the teacher's webpage: http://ricerca.mat.uniroma3.it/users/vbonifaci/in440.html

Type of evaluation

Oral exam.