We investigate a planning problem arising in the forthcoming Digital Video Broadcasting (DVB-T) system. Unlike current analog systems, the DVB-T standard allows a mitigation of the interference by means of a suitable synchronization of the received signals. The problem we describe in this paper is that of finding a time offset to impose to the signal emitted by each transmitter of the network, so as to maximize the network (territory) coverage (Time Offset Problem, TOP). We show that, unlike related problems in which other transmitter parameters are taken as decision variables (e.g., emission powers or frequencies), TOP has a nice and algorithmically exploitable combinatorial structure. Namely, we introduce an exponentially sized Set Covering formulation of TOP, in which constraints are dynamically generated by a polynomial time oracle. We show the effectiveness of the approach through extensive experiments on the reference test bed of the Italian DVB-T Frequency Plan.
Citation
Discrete Applied Mathematics, (156/3), February 2008, 339--351