PhD School Lecture, 08/02/2021, 16:15 - 18:00 and 09/02/2021, 14:00 - 16:00
Department of Electrical, Electronic and Information Engineering
University of Bologna
Lecture
A gentle introduction to approximation algorithms
Most relevant optimization problems are NP-hard, which makes their exact solution extremely difficult both from a theoretical and from a practical viewpoint.
Therefore, a natural question concerns the quality of the approximation one can obtain using polynomial-time heuristic algorithms. Within these settings, we will introduce the concept of worst-case performance ratio associated with an algorithm used to solve a given problem and we will analyze the performance of a number of simple algorithms under this metric. Finally, we will show that, besides the classical computational complexity, optimization problems can be classified according to their approximability: while some problems do not allow any kind of approximation, other problems can be approximated to any required degree using a polynomial time approximation scheme (PTAS).
Lecture Monaci - Approximation Algorithms
Biosketch
Michele Monaci got a PhD degree in system engineering in 2002 from the University of Bologna.
From 2005 to 2016 he was assistant professor at the University of Padova.
In 2016 he joined the Department of Electrical, Electronic and Information Engineering of the University of Bologna, where he became full professor of Operations Research in 2019.
His research activity concerns the design and analysis of models and algorithms for packing and loading problems, crew scheduling and railways applications, and the design and implementation of exact and heuristic algorithms for Mixed-Integer Linear Programming problems.