Frequency capping in online advertising (extended abstract)

Niv Buchbinder, Moran Feldman, Arpita Ghosh, Joseph Naor

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

We study the following online problem. Each advertiser ai has a value vi, demand di, and frequency cap fi. Supply units arrive online, each one associated with a user. Each advertiser can be assigned at most di units in all, and at most fi units from the same user. The goal is to design an online allocation algorithm maximizing total value. We first show a deterministic upper bound of 3/4-competitiveness, even when all frequency caps are 1, and all advertisers share identical values and demands. A competitive ratio approaching 1 - 1/e can be achieved via a reduction to a model with arbitrary decreasing valuations [GM07]. Our main contribution is analyzing two 3/4-competitive greedy algorithms for the cases of equal values, and arbitrary valuations with equal demands. Finally, we give a primal-dual algorithm which may serve as a good starting point for improving upon the 1 - 1/e ratio.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفAlgorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings
الصفحات147-158
عدد الصفحات12
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2011
منشور خارجيًانعم
الحدث12th International Symposium on Algorithms and Data Structures, WADS 2011 - New York, NY, الولايات المتّحدة
المدة: ١٥ أغسطس ٢٠١١١٧ أغسطس ٢٠١١

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت6844 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

!!Conference

!!Conference12th International Symposium on Algorithms and Data Structures, WADS 2011
الدولة/الإقليمالولايات المتّحدة
المدينةNew York, NY
المدة١٥/٠٨/١١١٧/٠٨/١١

ملاحظة ببليوغرافية

Funding Information:
Moran Feldman is a recipient of the Google Europe Fellowship in Market Algorithms, and this research is supported in part by this Google Fellowship. This work was supported in part by ISF grant 1366/07 and the Google Interuniversity center for Electronic Markets and Auctions.

Funding Information:
★ Moran Feldman is a recipient of the Google Europe Fellowship in Market Algorithms, and this research is supported in part by this Google Fellowship. ★★This work was supported in part by ISF grant 1366/07 and the Google Inter-university center for Electronic Markets and Auctions. 1 In contrast, sponsored search advertisers typically pay per click or per action, and usually have budgets, rather than demands, or quotas, on the number of impressions.

بصمة

أدرس بدقة موضوعات البحث “Frequency capping in online advertising (extended abstract)'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا