Unit APPROXIMATION ALGORITHMS

Course
Informatics
Study-unit Code
55A02077
Curriculum
In all curricula
Teacher
Alfredo Navarra
Teachers
  • Alfredo Navarra
Hours
  • 42 ore - Alfredo Navarra
CFU
6
Course Regulation
Coorte 2020
Offered
2021/22
Learning activities
Affine/integrativa
Area
Attività formative affini o integrative
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
Condividi su