Algoritmi online
Teacher
Gaia Nicosia
Abstract
Le tecniche classiche dell’ottimizzazione combinatoria forniscono un potente strumento per la risoluzione di problemi complessi che nascono da diverse applicazioni. Le tecniche tradizionali dell’ottimizzazione assumono, in generale, che la conoscenza dei dati di input sia completa. Tuttavia, esistono molti casi in cui devono essere prese delle decisioni in tempo reale, prima che un’informazione completa sull’input sia nota. Spesso, si deve produrre parte della soluzione del problema, non appena una “nuova parte di informazione” diventa nota. Questa situazione viene detta online e un algoritmo viene detto online se prende decisioni, ossia produce un output, senza la conoscenza completa dell’input. I problemi online nascono in contesti applicativi quali ad esempio l’allocazione di risorse nei sistemi operativi, robotica, organizzazione dei dati, scheduling e sistemi distribuiti.
In questo corso, basandosi sui contenuti del libro “Online Computation and Competitive Analysis” di A. Borodin e R. El-Yaniv, verranno fornite le nozioni di base e presentate le tecniche più importanti usate nell’analisi degli algoritmi online. Verranno poi analizzati alcuni problemi che nascono in contesti applicativi.
Program
1. Definizione di algoritmi online
2. Primi esempi di analisi competitiva
3. Cenni a problemi di paging, scheduling, routing, packing
4. Cenni agli algoritmi randomizzati
Primary Material “Online Computation and Competitive Analysis” di A. Borodin e R. El-Yaniv, slide del corso e articoli scientifici
