Unit APPROXIMATION ALGORITHMS
- Course
- Informatics
- Study-unit Code
- 55A02077
- Curriculum
- Modelli e sistemi dell'elaborazione dell'informazione
- Teacher
- Alfredo Navarra
- Teachers
-
- Alfredo Navarra
- Hours
- 42 ore - Alfredo Navarra
- CFU
- 6
- Course Regulation
- Coorte 2019
- Offered
- 2020/21
- Learning activities
- Caratterizzante
- Area
- Discipline informatiche
- Academic discipline
- INF/01
- Type of study-unit
- Opzionale (Optional)
- Type of learning activities
- Attività formativa monodisciplinare
- Language of instruction
- Italian
- Contents
- Introduction to approximation algorithms Basic problems and corresponding complexity studies:
Knapsack; Vertex Cover; Minimum Hitting Set; Matching;
TSP; Facility Location; k-Center; Scheduling
Recent scientific papers investigations:
Automated Trading; Drone positioning; Multi-Interface networks
Open problems, discussions and proposals - Reference texts
- The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys, Cambridge University Press.
- Educational objectives
- Advanced knowledge about approximation algorithms issues. Increasing critical and application skills
- Prerequisites
- basic knowledge on algorithms
- Teaching methods
- lectures,round tables with students
- Learning verification modality
- oral exam, seminar
- Extended program
- Introduction to approximation algorithms Basic problems and corresponding complexity studies:
Knapsack; Vertex Cover; Minimum Hitting Set; Matching;
TSP; Facility Location; k-Center; Scheduling
Recent scientific papers investigations:
Automated Trading; Drone positioning; Multi-Interface networks
Open problems, discussions and proposals