This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Gaur, D. R. Articles by Kohli, R.

Conflict Resolution in the Scheduling of Television Commercials

Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, Alberta T1K 3M4, Canada
School of Computing Science, Simon Fraser University, Burnaby, British Columbia V5A 1S6, Canada
Graduate School of Business, Columbia University, New York, New York 10027
gaur{at}cs.uleth.ca
ramesh{at}cs.sfu.ca
rk35{at}columbia.edu

We extend a previous model for scheduling commercial advertisements during breaks in television programming. The proposed extension allows differential weighting of conflicts between pairs of commercials. We formulate the problem as a capacitated generalization of the max k-cut problem in which the vertices of a graph correspond to commercial insertions and the edge weights to the conflicts between pairs of insertions. The objective is to partition the vertices into k capacitated sets to maximize the sum of conflict weights across partitions. We note that the problem is NP-hard. We extend a previous local-search procedure to allow for the differential weighting of edge weights. We show that for problems with equal insertion lengths and break durations, the worst-case bound on the performance of the proposed algorithm increases with the number of program breaks and the number of insertions per break, and that it is independent of the number of conflicts between pairs of insertions. Simulation results suggest that the algorithm performs well even if the problem size is small.

Subject classifications: marketing; advertising; media; networks/graphs; maxcut; heuristics.
History: Received April 2007; revision received November 2007; accepted December 2007.