Caricamento in corso...
Computational complexity and approximation
01WAVUQ
A.A. 2025/26
Course Language
Inglese
Degree programme(s)
Doctorate Research in Ingegneria Gestionale E Della Produzione - Torino
Course structure
| Teaching | Hours |
|---|---|
| Lezioni | 20 |
Lecturers
| Teacher | Status | SSD | h.Les | h.Ex | h.Lab | h.Tut | Years teaching |
|---|---|---|---|---|---|---|---|
| Della Croce Di Dojola Federico | Professore Ordinario | MATH-06/A | 20 | 0 | 0 | 0 | 1 |
Co-lectures
Context
| SSD | CFU | Activities | Area context | *** N/A *** | 4 |
|---|
Il corso mira a fornire un'introduzione alla complessità computazionale e all'approssimazione per problemi di ottimizzazione combinatoria, con particolare attenzione ai problemi di schedulazione e sequenziamento. La schedulazione come area di ricerca è motivata dalla sua applicazione pratica nella pianificazione della produzione (schedulazione di officina), nell’informatica e nei sistemi di telecomunicazioni (schedulazione real-time e gestione di risorse condivise). La schedulazione costituisce ad oggi una branca molto importante della Ricerca Operativa e dell’Ottimizzazione Combinatoria. In generale, la schedulazione è relativa all’allocazione ottima ad attività di risorse scarse nel tempo. Il Corso si propone di fornire le conoscenze di base sui modelli ed algoritmi di schedulazione con enfasi sulla competenze relative alla complessità computazionale e degli algoritmi di approssimazione. Verranno analizzati i principali modelli di schedulazione risolvibili con algoritmi polinomiali, si esporranno i concetti di base di complessità computazionale e verranno introdotti i principali schemi di approssimazione polinomiale. Verranno dati esempi di algoritmi approssimati per problemi paradigmatici.
Aim of the course is to provide an introduction to computational complexity and approximation for combinatorial optimization problems with emphasis on sequencing and scheduling problems. Scheduling as a research area is motivated by its practical application in production planning (machine scheduling) and in computer science and telecommunications systems (real-time scheduling and management of shared resources). Due to its practical relevance, scheduling is nowadays a fairly important branch of the Operations Research and Combinatorial Optimization research areas. In general, scheduling concerns the optimal allocation of scarce resources to activities over time. The main polynomially solvable scheduling models will be introduced, basics on computational complexity will be provided and polynomial time approximation schemes will be presented with examples of approximation approaches for paradigmatic problems.
Competenze di Ricerca Operativa e Ottimizzazione
Competences in Operations Research and Optimization
Complessità computazionale:
• Algoritmi polinomiali
• Classi di complessità P e NP
• NP-completezza in senso forte ed in senso debole
• Riduzioni polinomiali
• Algoritmi esatti esponenenziali
Approssimazione:
• Approssimazione polinomiale
• PTAS e FPTAS
• Inapprossimabilità
• Cenni sull’approssimazione esponenziale
Introduzione ai problemi di schedulazione
• Three-field Classificazione in 3 campi
• Problemi di schedulazione risolubili in tempo polinomiale
• Rapporti di approssimazione costanti in schedulazione
• Computational complexity:
• polynomial time algorithms
• P and NP complexity classes
• Strong and Weak NP-completeness
• Polynomial time reductions
• Exact exponential algorithms
Approximation:
• Polynomial time approximation
• PTAS and FPTAS
• Introduction to sequencing and scheduling
• Three-field classification
• Polynomially solvable machine scheduling problems
• Constant approximation ratios in scheduling
In presenza
On site
Presentazione report scritto - Sviluppo di project work in team
Written report presentation - Team project work development
P.D.1-1 - Novembre
P.D.1-1 - November
L'esame sarà costituito da una prova scritta o da un project work in funzione del numero delle persone iscritte al corso
The exam will consist of a written test or a project work depending on the number of people enrolled in the course