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/2014 Zur Ausgabe

Premium Partner

BranchenIndex Online

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

Whitepaper

- ANZEIGE -

Wie können Sie Stress im Fernstudium bewältigen?

Ein Fernstudium erfordert ein hohes Maß an Selbstorganisation und Disziplin. Das bedeutet oft Stress - Prüfungsstress, Abgabetermine, Zeitdruck… Stress wird dann zum Problem, wenn wir ihn nicht mehr im Griff haben. Wenn wir die Ursachen und auch Auswirkungen von Stress verstehen, ist das ein wichtiger Schritt hin zu einem erfolgreichen Stressmanagement. Lesen Sie in diesem Auszug aus dem Fachbuch "Stressmanagement im Fernstudium" wie Sie Ihren Stress effektiv bewältigen können. Inklusive Selbsttest.
Jetzt gratis downloaden!

Bildnachweise