Il problema di Babbo Natale

Nella notte di Natale, Babbo Natale sale sulla sua slitta per distribuire i regali intorno al mondo. Approfondito il problema della velocità della slitta e delle dimensioni del sacco di Babbo, c'è in effetti un altro problema, strettamente legato ai regali, che è stato affrontato nel 2006 in un importante articolo scientifico:

Babbo Natale ha \(n\) regali da consegrare tra \(m\) bambini. Ogni bambino assegna un valore arbitrario a ciascun regalo. Sia \(p_{ij}\) il valore che il bambino \(i\) assegna al regalo \(j\). L'obiettivo di Babbo Natale è distribuire i regali in modo tale che ogni bambino fortunato sia il più felice possibile, ovvero deve cercare di massimizzare \[\min_{i=1, \cdots, m} \sum_{j \in S_i} p_{ij}\] dove \(S_i\) è l'insieme dei regali ricevuti dall'\(i\)-esimo bambino.

In effetti, come nei classici giochi matematici, questa formulazione nasconde un problema matematico più profondo, quello delle macchine parallele. Questo è un problema di tipo NP, che può essere affrontato solo in maniera approssimata, che poi è come viene affrontato dai due autori dell'articolo di cui sopra, Nikhil Bansal e Maxim Sviridenko.
Questo ha come conseguenza che non è detto che esista un tempo polinomiale che permetta a un algoritmo di risolvere il problema di Babbo Natale. Per tempo polinomiale si intende un tempo di esecuzione dell'algoritmo che viene descritto da una espressione polinomiale, con un polinomio di grado \(k\), con \(k\) una costante arbitrariamente grande. E anche se esistesse, non è detto che questo tempo sia sufficientemente breve per ottenere una soluzione.
In questo contesto, l'obiettivo dell'articolo è determinare un algoritmo che permetta a un qualsiasi computer di determinare una soluzione al problema di Babbo Natale. A cui, personalmente, continuo a consigliare di affidarsi alle letterine: sistema più antiquato, ma indubbiamente più affidabile!

---

Immagine di apertura realizzata con NightCafe