Conflict Resolution in the Scheduling of Television Commercials

Daya Ram Gaur (), Ramesh Krishnamurti () and Rajeev Kohli ()
Additional contact information
Daya Ram Gaur: Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, Alberta T1K 3M4, Canada
Ramesh Krishnamurti: School of Computing Science, Simon Fraser University, Burnaby, British Columbia V5A 1S6, Canada
Rajeev Kohli: Graduate School of Business, Columbia University, New York, New York 10027

Operations Research, 2009, vol. 57, issue 5, 1098-1105

Abstract: 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.

Keywords: marketing; advertising; media; networks/graphs; maxcut; heuristics (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1080.0635 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:57:y:2009:i:5:p:1098-1105

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().