Study-unit APPROXIMATION ALGORITHMS
| Course name | Informatics |
|---|---|
| Study-unit Code | 55A02077 |
| Curriculum | Comune a tutti i curricula |
| Lecturer | Alfredo Navarra |
| Lecturers |
|
| Hours |
|
| CFU | 6 |
| Course Regulation | Coorte 2023 |
| Supplied | 2024/25 |
| Supplied other course regulation | |
| Learning activities | Affine/integrativa |
| Area | Attività formative affini o integrative |
| Sector | 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 |