Online allocation of display advertisements subject to advanced sales contracts

Saeed Alaei; Esteban Arcaute; Samir Khuller; Wenjing Ma; Azarakhsh Malekian; John Tomlin

doi:10.1145/1592748.1592758

Online allocation of display advertisements subject to advanced sales contracts

Saeed Alaei^*, Esteban Arcaute, Samir Khuller, Wenjing Ma, Azarakhsh Malekian, John Tomlin

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

18 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Proceedings of the 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09
Pages	69-77
Number of pages	9
DOIs	https://doi.org/10.1145/1592748.1592758
State	Published - 2009
Event	3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09 - Paris, France Duration: Jun 28 2009 → Jun 28 2009

Publication series

Name	Proceedings of the 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09

Conference

Conference	3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09
Country/Territory	France
City	Paris
Period	6/28/09 → 6/28/09

Keywords

Display advertising
Online algorithms
Optimization
Simulation

ASJC Scopus subject areas

Artificial Intelligence
Computer Science Applications
Software

Access to Document

10.1145/1592748.1592758

Cite this

Alaei, S., Arcaute, E., Khuller, S., Ma, W., Malekian, A., & Tomlin, J. (2009). Online allocation of display advertisements subject to advanced sales contracts. In Proceedings of the 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09 (pp. 69-77). Article 1592758 (Proceedings of the 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09). https://doi.org/10.1145/1592748.1592758

Alaei, Saeed ; Arcaute, Esteban ; Khuller, Samir et al. / Online allocation of display advertisements subject to advanced sales contracts. Proceedings of the 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09. 2009. pp. 69-77 (Proceedings of the 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09).

@inproceedings{ee9f3b83508c4c5db088a7fccbf2a4d2,

title = "Online allocation of display advertisements subject to advanced sales contracts",

abstract = "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.",

keywords = "Display advertising, Online algorithms, Optimization, Simulation",

author = "Saeed Alaei and Esteban Arcaute and Samir Khuller and Wenjing Ma and Azarakhsh Malekian and John Tomlin",

year = "2009",

doi = "10.1145/1592748.1592758",

language = "English (US)",

isbn = "9781605586717",

series = "Proceedings of the 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09",

pages = "69--77",

booktitle = "Proceedings of the 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09",

note = "3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09 ; Conference date: 28-06-2009 Through 28-06-2009",

}

Alaei, S, Arcaute, E, Khuller, S, Ma, W, Malekian, A & Tomlin, J 2009, Online allocation of display advertisements subject to advanced sales contracts. in Proceedings of the 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09., 1592758, Proceedings of the 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09, pp. 69-77, 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09, Paris, France, 6/28/09. https://doi.org/10.1145/1592748.1592758

Online allocation of display advertisements subject to advanced sales contracts. / Alaei, Saeed; Arcaute, Esteban; Khuller, Samir et al.
Proceedings of the 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09. 2009. p. 69-77 1592758 (Proceedings of the 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Online allocation of display advertisements subject to advanced sales contracts

AU - Alaei, Saeed

AU - Arcaute, Esteban

AU - Khuller, Samir

AU - Ma, Wenjing

AU - Malekian, Azarakhsh

AU - Tomlin, John

PY - 2009

Y1 - 2009

N2 - 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.

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.

KW - Display advertising

KW - Online algorithms

KW - Optimization

KW - Simulation

UR - http://www.scopus.com/inward/record.url?scp=70449623572&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70449623572&partnerID=8YFLogxK

U2 - 10.1145/1592748.1592758

DO - 10.1145/1592748.1592758

M3 - Conference contribution

AN - SCOPUS:70449623572

SN - 9781605586717

T3 - Proceedings of the 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09

SP - 69

EP - 77

BT - Proceedings of the 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09

T2 - 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09

Y2 - 28 June 2009 through 28 June 2009

ER -

Alaei S, Arcaute E, Khuller S, Ma W, Malekian A, Tomlin J. Online allocation of display advertisements subject to advanced sales contracts. In Proceedings of the 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09. 2009. p. 69-77. 1592758. (Proceedings of the 3rd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD 2009 in Conjunction with SIGKDD'09). doi: 10.1145/1592748.1592758

Online allocation of display advertisements subject to advanced sales contracts

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this