Infostations.

In [C5], è studiato il problema di minimizzare il numero di processori necessari in una infostation per servire on-line e senza ritardo le richieste degli utenti che l'attraversano. Ogni richiesta è caratterizzata da una durata e da un tipo. Ogni processore può soddisfare simultaneamente al più $k$ richieste di cui al più $h_c$ dello stesso tipo $c$. Si mostra che il problema è NP-hard, e si danno algoritmi approssimati di complessità polinomiale.