New Formulations for the Conflict Resolution Problem in the Scheduling of Television Commercials

References

• Anjos MF, Ghaddar B, Hupp L, Liers F, Wiegele A (2013) Solving k-way graph partitioning problems to optimality: The impact of semidefinite relaxations and the bundle method. Junger M, Reinelt G, eds. Facets of Combinatorial Optimization (Springer, Berlin), 355–386.Crossref, Google Scholar
• Araman VF, Popescu I (2010) Media revenue management with audience uncertainty: Balancing upfront and spot market sales. Manufacturing Service Oper. Management 12(2):190–212.Link, Google Scholar
• Bai R, Xie J (2006) Heuristic algorithms for simultaneously accepting and scheduling advertisements on broadcast television. J. Inform. Comput. Sci. 1(4):245–251.Google Scholar
• Billionnet A, Costa MC, Sutter A (1992) An efficient algorithm for a task allocation problem. J. ACM 39(3):502–518.Crossref, Google Scholar
• Bollapragada S, Garbiras M (2004) Sheduling commercials on broadcast television. Oper. Res. 52(3):337–345.Link, Google Scholar
• Bollapragada S, Mallik S (2008) Managing on-air ad inventory in broadcast television. IIE Trans. 40(12):1107–1123.Crossref, Google Scholar
• Bollapragada S, Bussieck MR, Mallik S (2004) Scheduling commercial videotapes in broadcast television. Oper. Res. 52(5):679–689.Link, Google Scholar
• Bollapragada S, Cheng H, Phillips M, Garbiras M, Scholes M, Gibbs T, Humphreville M (2002) NBC’s optimization systems increase revenues and productivity. Interfaces 32(1):47–60.Link, Google Scholar
• Brusco MJ (2008) Scheduling advertising slots for television. J. Oper. Res. Soc. 59(10):1363–1372.Crossref, Google Scholar
• Burkard R, Dell’Amico M, Martello S (2009) Assignment Problems (SIAM, Philadelphia).Crossref, Google Scholar
• Eisenblatter A (2002) The semidefinite relaxation of the k-partition polytope is strong. Cook WJ, Schulz AS, eds. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 2337 (Springer, Berlin), 273–290.Crossref, Google Scholar
• Ernst A, Jiang H, Krishnamoorthy M (2006) Exact solutions to task allocation problems. Management Sci. 52(10):1634–1646.Link, Google Scholar
• Frieze A, Jerrum M (1997) Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Algorithmica 18(1):67–81.Crossref, Google Scholar
• Gaur DR, Krishnamurti R, Kohli R (2008) The capacitated max k-cut problem. Math. Programming 115(1):65–72.Crossref, Google Scholar
• Gaur DR, Krishnamurti R, Kohli R (2009) Conflict resolution in the scheduling of television commercials. Oper. Res. 57(5):1098–1105.Link, Google Scholar
• Ghaddar B, Anjos MF, Liers F (2011) A branch-and-cut algorithm based on semidefinite programming for the minimum k-partition problem. Ann. Oper. Res. 188(1):155–174.Crossref, Google Scholar
• Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6):1115–1145.Crossref, Google Scholar
• Hadj-Alouane AB, Bean JC, Murty KG (1999) A hybrid genetic/optimization algorithm for a task allocation problem. J. Scheduling 2(4):189–201.Crossref, Google Scholar
• Kimms A, Muller-Bungart M (2006) Revenue management for broadcasting commercials: The channel’s problem of selecting and scheduling the advertisements to be aired. Internat. J. Revenue Management 1(1):28–44.Crossref, Google Scholar
• Reddy SK, Aronson JE, Stam A (1998) SPOT: Scheduling programs optimally for television. Management Sci. 44(1):83–102.Link, Google Scholar
• Wolkowicz H, Zhao Q (1999) Semidefinite programming relaxations for the graph partitioning problem. Discrete Appl. Math. 96–97:461–479.Crossref, Google Scholar
• Zhang X (2006) Mathematical models for the television advertising allocation problem. Internat. J. Oper. Res. 1(3):302–322.Crossref, Google Scholar