TY - CONF T1 - Online allocation of display advertisements subject to advanced sales contracts T2 - Proceedings of the Third International Workshop on Data Mining and Audience Intelligence for Advertising Y1 - 2009 A1 - Alaei,Saeed A1 - Arcaute,Esteban A1 - Khuller, Samir A1 - Ma,Wenjing A1 - Malekian,Azarakhsh A1 - Tomlin,John KW - display advertising KW - modeling KW - online algorithms KW - OPTIMIZATION KW - simulation AB - In this paper we propose a utility model that accounts for both sales and branding advertisers. We first study the computational complexity of optimization problems related to both online and offline allocation of display advertisements. Next, we focus on a particular instance of the online allocation problem, and design a simple online algorithm with provable approximation guarantees. Our algorithm is near optimal as is shown by a matching lower bound. Finally, we report on experiments to establish actual case behavior on some real datasets, with encouraging results. JA - Proceedings of the Third International Workshop on Data Mining and Audience Intelligence for Advertising T3 - ADKDD '09 PB - ACM CY - New York, NY, USA SN - 978-1-60558-671-7 UR - http://doi.acm.org/10.1145/1592748.1592758 M3 - 10.1145/1592748.1592758 ER -