Heuristics and approximation algorithms for scheduling advertisements problem

Author(s)

Mauro Roberto Costa da Silva

• Document type: Master's Dissertation
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2019-03-20

Examining board members

Rafael Crivellari Saliba Schouery; Kelly Cristina Poldi; Eduardo Candido Xavier

• Advisor: Lehilton Lelis Chaves Pedrosa; Rafael Crivellari Saliba Schouery

Abstract

In the MAXSPACE problem, given a set of ads A, one wants to place a subset A' of A into K slots B_1, ..., B_K of size L. Each advertisement A_i in A has a size s_i and a frequency w_i. A schedule is feasible if the total size of ads in any slot is at most L, and each ad A_i in A' appears in exactly w_i slots with at most one copy per slot. The objective is to find a feasible schedule which maximizes the sum of the space occupied by all slots. We introduce some generalizations for this problem, such as MAXSPACE-R, MAXSPACE-RD, and MAXSPACE-RDWV. We consider the MAXSPACE-RD with a constant number of slots and present a polynomial-time approximation scheme, i.e., for any ? > 0, we give a polynomial-time algorithm which returns a solution with value at least (1-?)OPT, where OPT is the optimal value. We also present a 1/9-approximation for MAXSPACE-R with a polynomial number of slots. We implement the metaheuristics Greedy Randomized Adaptive Search Procedure, Variable Neighborhood Search, Variable Neighborhood Descent, Tabu Search and Local Search for MAXSPACE and MAXSPACE-RDWV. The computational results of these heuristics were compared with the results of the hybrid genetic algorithm proposed by Kumar et al (AU)

• FAPESP's process: 17/21297-2 - Advertisements scheduling problems
• Grantee: Mauro Roberto Costa da Silva
• Support Opportunities: Scholarships in Brazil - Master