Seminario prof. Pferschy

Il prossimo giovedì 9 aprile alle ore 15.00, presso la sala riunioni della Sezione di Informatica e Automazione del DICITA dell’Università degli Studi Roma Tre, il prof. Ulrich Pferschy, dell’Università di Graz, terrà un seminario dal titolo:

On the Advertisement Knapsack Problem

Abstract: The Advertisement Knapsack Problem (AKP) models the simultaneous selection and scheduling of TV advertisements within a commercial break. The profit generated by an advertisement depends not only on its revenue rate and duration but also on its placement within the break, captured by a time-dependent impact function. This position-dependent valuation yields a non-standard generalization of the classical 0-1 Knapsack Problem. Focusing on the practically relevant case of negative unimodal impact functions (higher audience attention at the beginning and end of a break), we discuss complexity issues and describe two MILP models, along with their optimality gaps, as well as a dynamic programming algorithm. Finally, we present a composite greedy algorithm offering a tight approximation guarantee of 3.
(joint work with Michele Monaci)