Scheduling space-sharing for internet advertising.

*(English)*Zbl 1014.90034Summary: This paper provides the first in-depth study of the algorithmic questions involved in the scheduling of space-sharing for Internet advertising. We consider the scheduling problem where each advertisement is specified by a geometry and a display frequency. Given a set of ads, a schedule of the ads specifies which ads are to be displayed at the same time. The objective is find a schedule of the ads such that (1) each ad is displayed with the correct frequency, (2) each ad is allocated enough space for the specified geometry, (3) all the ads to be displayed simultaneously can be arranged in the space available for advertising. We demonstrate that an optimal schedule can be determined by finding a solution to a new variant of the bin packing problem that we introduce. In this new variant, there are a number of copies of each item to be placed into the bins. In addition to the usual bin packing requirements, all copies of an item must be placed in different bins. In this paper, we provide an efficient algorithm that finds the optimal solution to a restricted version of the new bin packing problem. This algorithm also provides a 2-approximation for the unrestricted case. We then apply this approximation to the problem of scheduling space-sharing for Internet advertising. We obtain a 2-approximation to the problem of minimizing the space requirements of a given set of ads, as well as to the problem of determining the best subset of the ads that can be scheduled with a given space constraint. We also consider an on-line version of the ad scheduling problem, where requests to purchase ad space arrive sequentially and after each request arrives, a decision must be made whether or not to sell the requested space without knowledge of future requests. We provide an algorithm that makes these decisions in a manner that is the best possible for any on-line algorithm.

Full Text:
DOI

##### References:

[1] | Homepage of DoubleClick. See: http://www.doubleclick.net, 1998. |

[2] | Homepage of NetGravity. See: http://www.netgravity.com, 1998. |

[3] | Homepage of W3.COM. See: http://www.w3.com/home, 1998. |

[8] | Resource scheduling for parallel database and scientific applications. In Proceedings of the Eighth ACM Symposium on Parallel Algorithms and Architectures June 1996; 329-335. |

[10] | Optimal online scheduling of parallel jobs with dependencies. In Proceedings of the 25th ACM Symposium on the Theory of Computing 1993; 642-651. · Zbl 1310.68251 |

[11] | Scheduling to minimize average completion time: Off-line and on-line algorithms. In Proceedings of the Seventh ACM-SIAM Symposium on Discrete Algorithms 1996; 142-151. · Zbl 0845.90071 |

[12] | Scheduling malleable and nonmalleable parallel tasks. In Proceedings of the Fifth ACM-SIAM Symposium on Discrete Algorithms 1994; 167-176. · Zbl 0873.68004 |

[13] | Scheduling parallel machines online. In Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science 1991; 131-140. |

[14] | Scheduling parallel tasks to minimize average response time. In Proceedings of the Fifth ACM-SIAM Symposium on Discrete Algorithms 1994; 112-121. · Zbl 1114.68337 |

[15] | Approximate algorithms for scheduling parallelizable tasks. In Proceeding of the Fourth ACM Symposium on Parallel Algorithms and Architectures, 1992; 323-332. |

[17] | Bellcore. Adapt/x advertiser(tm) product overview. See http://www.bellcore.com/ADAPTX/ADVERTISER/index.htm, 1998. |

[18] | Biased random walks, lyapunov functions, and stochastic analysis of best fit bin packing. Proceedings of the Seventh ACM-SIAM Symposium on Discrete Algorithms 1996; 351-358. · Zbl 0853.68092 |

[19] | Homepage of PointCast. See: http://www.pointcast.com, 1998. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.