Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.08.2014 | Ausgabe 4/2014

Journal of Scheduling 4/2014

Frequency capping in online advertising

Zeitschrift:
Journal of Scheduling > Ausgabe 4/2014
Autoren:
Niv Buchbinder, Moran Feldman, Arpita Ghosh, Joseph Naor
Wichtige Hinweise
A preliminary version of this paper appeared in the Proceedings of the Algorithms and Data Structures Symposium (WADS), New York, NY, 2011.

Abstract

We study the following online problem. There are n advertisers. Each advertiser \(a_i\) has a total demand \(d_i\) and a value \(v_i\) for each supply unit. Supply units arrive one by one in an online fashion, and must be allocated to an agent immediately. Each unit is associated with a user, and each advertiser \(a_i\) is willing to accept no more than \(f_i\) units associated with any single user (the value \(f_i\) is called the frequency cap of advertiser \(a_i\)). The goal is to design an online allocation algorithm maximizing the total value. We first show a deterministic \(3/4\)-competitiveness upper bound, which holds 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 different model considered by Goel and Mehta (WINE ‘07: Workshop on Internet and Network, Economics: 335–340, 2007). Our main contribution is analyzing two \(3/4\)-competitive greedy algorithms for the cases of equal values, and arbitrary valuations with equal integral demand to frequency cap ratios. Finally, we give a primal-dual algorithm which may serve as a good starting point for improving upon the ratio of \(1-1/e\).

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit dem Kombi-Abo erhalten Sie vollen Zugriff auf über 1,8 Mio. Dokumente aus mehr als 61.000 Fachbüchern und rund 500 Fachzeitschriften aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit dem Wirtschafts-Abo erhalten Sie Zugriff auf über 1 Mio. Dokumente aus mehr als 45.000 Fachbüchern und 300 Fachzeitschriften aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb

Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 4/2014

Journal of Scheduling 4/2014Zur Ausgabe

Premium Partner

Stellmach & BröckersBBL | Bernsau BrockdorffMaturus Finance GmbHPlutahww hermann wienberg wilhelm

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Künstliche Intelligenz und der Faktor Arbeit - Implikationen für Unternehmen und Wirtschaftspolitik

Künstliche Intelligenz und ihre Auswirkung auf den Faktor Arbeit ist zum Modethema in der wirtschaftswissenschaftlichen Politikberatung avanciert. Studien, die alarmistisch die baldige Verdrängung eines Großteils konventioneller Jobprofile beschwören, leiden jedoch unter fragwürdiger Datenqualität und Methodik. Die Unternehmensperspektive zeigt, dass der Wandel der Arbeitswelt durch künstliche Intelligenz weitaus langsamer und weniger disruptiv ablaufen wird. Jetzt gratis downloaden!

Bildnachweise