2025-11-23T02:01:16.750653

Multi-product Influence Maximization in Billboard Advertisement

Ali, Islam, Banerjee
Billboard Advertisement has emerged as an effective out-of-home advertisement technique where the goal is to select a limited number of slots and play advertisement content over there with the hope that this will be observed by many people, and effectively, a significant number of them will be influenced towards the brand. Given a trajectory and a billboard database and a positive integer $k$, how can we select $k$ highly influential slots to maximize influence? In this paper, we study a variant of this problem where a commercial house wants to make a promotion of multiple products, and there is an influence demand for each product. We have studied two variants of the problem. In the first variant, our goal is to select $k$ slots such that the respective influence demand of each product is satisfied. In the other variant of the problem, we are given with $\ell$ integers $k_1,k_2, \ldots, k_{\ell}$, the goal here is to search for $\ell$ many set of slots $S_1, S_2, \ldots, S_{\ell}$ such that for all $i \in [\ell]$, $|S_{i}| \leq k_i$ and for all $i \neq j$, $S_i \cap S_j=\emptyset$ and the influence demand of each of the products gets satisfied. We model the first variant of the problem as a multi-submodular cover problem and the second variant as its generalization. For solving the first variant, we adopt the bi-criteria approximation algorithm, and for the other variant, we propose a sampling-based approximation algorithm. Extensive experiments with real-world trajectory and billboard datasets highlight the effectiveness and efficiency of the proposed solution approach.
academic

Multi-Produkt-Einflussmaximierung in der Plakatwerbung

Grundinformationen

  • Papier-ID: 2510.09050
  • Titel: Multi-product Influence Maximization in Billboard Advertisement
  • Autoren: Dildar Ali (IIT Jammu), Rajibul Islam (Gandhi Institute for Technological Advancement), Suman Banerjee (IIT Jammu)
  • Klassifizierung: cs.DS (Datenstrukturen und Algorithmen), cs.DB (Datenbanken)
  • Veröffentlichungsdatum: 10. Oktober 2025 (arXiv-Preprint)
  • Papierlink: https://arxiv.org/abs/2510.09050

Zusammenfassung

Außenwerbeplakate haben sich als effektive Außenwerbetechnologie etabliert, mit dem Ziel, eine begrenzte Anzahl von Zeitfenstern auszuwählen und Werbeinhalte auszustrahlen, um von vielen Menschen beobachtet zu werden und die Einstellung einer beträchtlichen Anzahl von Personen zur Marke effektiv zu beeinflussen. Dieses Papier untersucht eine Variante dieses Problems: Handelsunternehmen möchten mehrere Produkte bewerben, wobei jedes Produkt Einflussanforderungen hat. Es werden zwei Problemvarianten untersucht: Die erste Variante zielt darauf ab, k Zeitfenster auszuwählen, sodass die entsprechenden Einflussanforderungen für jedes Produkt erfüllt werden; in der zweiten Variante werden ℓ ganze Zahlen k₁, k₂, ..., k_ℓ gegeben, und das Ziel ist es, ℓ disjunkte Zeitfenstermengen S₁, S₂, ..., S_ℓ zu finden, die die Einflussanforderungen für jedes Produkt erfüllen.

Forschungshintergrund und Motivation

Problemhintergrund

  1. Bedeutung der Außenwerbung: Handelsunternehmen geben typischerweise 7-10% ihrer Gesamteinnahmen für Werbung aus; Außenwerbeplakate sind aufgrund ihrer Renditegarantie und Benutzerfreundlichkeit eine effektive Methode
  2. Einschränkungen traditioneller Probleme: Bestehende Forschung konzentriert sich hauptsächlich auf die Einflussmaximierung eines einzelnen Werbetreibenden oder die Bedauernsminimierung zwischen mehreren Werbetreibenden
  3. Praktische Anforderungen: Handelsunternehmen müssen typischerweise mehrere heterogene Produkte gleichzeitig bewerben, wobei jedes Produkt auf verschiedene Kundengruppen abzielt

Forschungsmotivation

  • Praktische Anforderungen: In der Realität müssen Werbetreibende unterschiedliche Einflussanforderungen mehrerer Produkte innerhalb eines einheitlichen Budgets erfüllen
  • Theoretische Lücke: Die bestehende Literatur mangelt es an Forschung zum Multi-Produkt-Plakatwerbungs-Zeitfenster-Auswahlproblem
  • Technische Herausforderungen: Es ist erforderlich, die Gesamtkosten zu minimieren und gleichzeitig die Einflusseinschränkungen für jedes Produkt zu erfüllen

Kernbeiträge

  1. Problemberweiterung: Erweiterung des Einfluss-Zeitfenster-Auswahlproblems auf Multi-Produkt-Werbeszenarios mit Untersuchung zweier verwandter Problemvarianten
  2. Theoretische Modellierung: Modellierung der ersten Variante als Multi-Submodular-Überdeckungsproblem und der zweiten Variante als verallgemeinerte Version
  3. Algorithmusdesign:
    • Anwendung eines Dual-Kriterium-Approximationsalgorithmus für die erste Variante
    • Vorschlag eines stichprobenbasierten Approximationsalgorithmus für die zweite Variante
  4. Effizienzoptimierung: Entwicklung effizienter heuristischer Lösungen zur Bewältigung von Skalierungsproblemen
  5. Experimentelle Validierung: Umfangreiche Experimente auf echten Trajektorien- und Plakatwerbungsdatensätzen

Methodische Details

Aufgabendefinition

Eingabe:

  • Trajektoriendatenbank D: Enthält Benutzerstandort-Zeit-Informationen und Produktinteressen
  • Plakatwerbungsdatenbank B: Enthält Plakatwerbungsstandort, Zeitfenster und Kosteninformationen
  • Kostenfunktion c: BS → R⁺
  • Produktmenge P = {1,2,...,ℓ}

Zwei Problemvarianten:

  1. Common Multi-Product Slot Selection Problem:
    • Wählen Sie eine einzelne Zeitfenstermenge S ⊆ BS
    • Minimieren Sie die Gesamtkosten ∑_{s∈S} c(s)
    • Erfüllen Sie die Einschränkung: ∀j ∈ ℓ, I_j(S) ≥ k_j
  2. Disjoint Multi-Product Slot Selection Problem:
    • Wählen Sie ℓ disjunkte Zeitfenstermengen S₁, S₂, ..., S_ℓ
    • Erfüllen Sie: |S_j| ≤ k_j, S_i ∩ S_j = ∅ (i≠j), I_j(S_j) ≥ σ_j

Kerntechniken

1. Einflussmodellfunktion

Die Einflussmodellfunktion für Produkt j ist definiert als:

I_j(S) = ∑_{u_i∈U_j} [1 - ∏_{s_j∈S} (1 - Pr(s_j, u_i))]

wobei U_j die Menge der Benutzer ist, die sich für Produkt j interessieren, und Pr(s_j, u_i) die Einflusswahr­scheinlichkeit des Zeitfensters s_j für Benutzer u_i ist.

2. Submodularitätseigenschaften

Die Einflussmodellfunktion besitzt Submodularitätseigenschaften und erfüllt den Grenznutzenverlust:

f(A ∪ {e}) - f(A) ≥ f(B ∪ {e}) - f(B), ∀A ⊆ B

Algorithmusarchitektur

Algorithmus 1: Dual-Kriterium-Approximationsalgorithmus für Common Slot Selection

  1. Normalisierung: Normalisieren Sie die Einflussmodellfunktion jedes Produkts, sodass I_j(BS) = 1
  2. Kontinuierliches Greedy: Verwenden Sie multilineare Erweiterung zur Lösung von Bruchlösungen auf dem Matroid-Polytop
  3. Zufälliges Runden: Stichprobe ℓ = ⌈log_{1/(1-ε)}(r)⌉ zufälliger Teilmengen
  4. Reparaturschritt: Fügen Sie für Produkte, die Einschränkungen nicht erfüllen, gierig Zeitfenster hinzu

Algorithmus 2: Stichprobenalgorithmus für Disjoint Slot Selection

  1. Permutationsstichprobe: Stichprobe zufälliger Permutationen von Produkt-Zeitfenster-Zuordnungen
  2. Gierige Zuweisung: Wählen Sie gierig Zeitfenster für jedes Produkt in Permutationsreihenfolge
  3. Machbarkeitsprüfung: Überprüfen Sie, ob alle Einschränkungen erfüllt sind
  4. Optimale Auswahl: Geben Sie die kostengünstigste machbare Lösung zurück

Technische Innovationspunkte

  1. Multilineare Erweiterungsanwendung: Anwendung der kontinuierlichen Erweiterungstechnik von Submodularfunktionen auf Multi-Produkt-Szenarien
  2. Stichprobenkomplexitätsanalyse: Verwendung der Hoeffding-Ungleichung zur Analyse der Stichprobenkomplexität des Stichprobenalgorithmus
  3. Dual-Kriterium-Approximation: Bereitstellung von Kostenannäherungsgarantien bei Erfüllung von Einflusseinschränkungen

Experimentelle Einrichtung

Datensätze

  1. New York City (NYC):
    • 227.428 Check-in-Datensätze (April 2012 - Februar 2013)
    • 1.083 eindeutige Benutzer
    • 716 Plakate, 1.031.040 Zeitfenster
  2. Los Angeles (LA):
    • 74.170 Check-in-Datensätze, 15 Straßen abdeckend
    • 2.000 eindeutige Benutzer
    • 1.483 Plakate, 2.135.520 Zeitfenster

Bewertungsmetriken

  • Einfluss: Gesamteinfluss, der von jedem Produkt erreicht wird
  • Zeitfensteranzahl: Gesamtzahl der Zeitfenster, die jedem Produkt zugewiesen werden
  • Berechnungszeit: Algorithmusausführungszeit
  • Kosten: Gesamtkosten der Zeitfensterauswahl

Vergleichsmethoden

  1. Random Allocation (RA): Zufällige Auswahl von Zeitfenstern zur Zuweisung an Produkte
  2. Top-k Allocation: Sortierung nach Einflussswert mit vorrangiger Zuweisung hocheinflussreicher Zeitfenster

Schlüsselparameter

  • Bedarfs-Angebots-Verhältnis α: Verhältnis der globalen Einflussanforderung zum Gesamtangebot (40%-120%)
  • Individuelles Bedarfsverhältnis β: Verhältnis der durchschnittlichen individuellen Anforderung zum Gesamtangebot (1%-20%)
  • Produktanzahl |P|: 5, 10, 20, 50, 100
  • Distanzparameter λ: 25m-150m
  • Approximationsparameter ε: 0,01-0,2

Experimentelle Ergebnisse

Hauptergebnisse

Einflussleistung

  • NYC-Datensatz: BCA-Methode 20-25% höher als Baseline-Methoden, RA-Methode zeigt beste Leistung
  • LA-Datensatz: BCA-Methode 8-10% höher als Baseline-Methoden
  • Wenn α≥100% und β≥10%, übersteigt die Nachfrage das Angebot; BCA-Methode übertrifft Baseline, aber RA-Methode hat keine machbare Lösung

Zeitfenster-Zuweisungseffizienz

  • Mit zunehmendem α und β steigt die Anzahl der Zeitfenster, die jedem Produkt zugewiesen werden
  • Top-k-Methode weist weniger Zeitfenster zu als Random-Methode
  • BCA-Methode weist mehr Zeitfenster zu als RA- und Baseline-Methoden (da alle Produktanforderungen erfüllt werden müssen)

Rechenkomplexität

  • Zeitkomplexität:
    • BCA-Algorithmus: O(n²ℓ/ε + nℓ)
    • RA-Algorithmus: O(|X|·ℓ·B_max/c_min·n·t)
  • RA-Methode hat längste Berechnungszeit (muss viele Permutationen berücksichtigen)
  • BCA-Methode hat moderate Zeit, wächst langsam mit α und β

Kosteneffizienz

  • RA-Methode zeigt optimale Kostenleistung und erfüllt alle Produktanforderungen mit minimalen Kosten
  • Mit zunehmenden Anforderungen steigen die Zuweisungskosten aller Methoden

Theoretische Garantien

Approximationsverhältnis des BCA-Algorithmus

Theorem: Sei r die Sparsität (maximale Anzahl von Funktionen, zu denen ein einzelnes Zeitfenster beitragen kann), ε > 0. Der BCA-Algorithmus gibt mit hoher Wahrscheinlichkeit eine Menge S zurück, die erfüllt:

  • Für alle j ∈ ℓ: I_j(S) ≥ (1 - 1/e - ε)·k_j
  • Erwartete Kosten: Ec(S) = O(1/ε·log r)·OPT

Stichprobenkomplexität

Theorem: Für beliebige ε,δ ∈ (0,1), wenn die Stichprobengröße ≥ ln(2/δ)·c(BS)²/(2ε²·(W_A)²), dann ist die Berechnungsabweichung kleiner als ε mit Wahrscheinlichkeit mindestens (1-δ).

Verwandte Arbeiten

Einfluss-Zeitfenster-Auswahl

  • Submodular-Graph-Methoden: Methoden basierend auf beschnittenen Submodular-Graphen
  • Branch-and-Bound-Framework: Exaktes Algorithmus-Framework
  • Gierige Lösungen: Gierige Algorithmen basierend auf Grenznutzen
  • Kooperative koevolutionäre Methoden: Von Wang et al. vorgeschlagene Methode

Bedauernsminimierung

  • Lokale Suchmethoden: Lokale Suchlösung von Zhang et al.
  • Regionale Einschränkungen: Bedauernsminimierung unter regionalen Einflusseinschränkungen von Ali et al.

Theoretische Grundlagen

  • Multi-Submodular-Überdeckungsproblem: Zufälliger Dual-Kriterium-Approximationsalgorithmus von Chekuri et al.
  • Kontinuierlicher Greedy-Algorithmus: Kontinuierliche Erweiterungstechnik für monotone Submodularfunktionen

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Problemmodellierung: Erfolgreiche Modellierung des Multi-Produkt-Plakatwerbungsproblems als Multi-Submodular-Überdeckungsproblem und dessen Verallgemeinerung
  2. Algorithmuseffektivität: Vorgeschlagene Algorithmen zeigen sowohl theoretisch als auch praktisch gute Leistung
  3. Praktischer Wert: Methode ist auf jedes Multi-Produkt-Außenwerbeszenario anwendbar

Einschränkungen

  1. Rechenkomplexität: Exponentielle Zeitkomplexität des RA-Algorithmus begrenzt Anwendung im großen Maßstab
  2. Annahmebedingungen: Annahme, dass Einflussmodellfunktionen Submodularität besitzen; in der Praxis möglicherweise nicht vollständig erfüllt
  3. Datenabhängigkeit: Erfordert genaue Trajektoriendaten und Benutzerproduktpräferenzinformationen
  4. Statisches Modell: Berücksichtigt keine Änderungen von Anforderungen und Angebot in dynamischen Umgebungen

Zukünftige Richtungen

  1. Dynamische Optimierung: Berücksichtigung zeitlich variierender Einflussanforderungen und Benutzerverhalten
  2. Online-Algorithmen: Entwicklung von Online-Optimierungsalgorithmen zur Verarbeitung von Echtzeit-Datenströmen
  3. Machine-Learning-Integration: Kombination mit Deep Learning zur Vorhersage von Benutzerinteressen und Einfluss
  4. Multi-Ziel-Optimierung: Gleichzeitige Berücksichtigung mehrerer Ziele wie Kosten, Abdeckung und Fairness

Tiefgehende Bewertung

Stärken

  1. Problemwichtigkeit: Löst wichtiges Problem in realen Geschäftsumgebungen mit klarem Anwendungswert
  2. Theoretische Strenge: Bietet vollständige theoretische Analyse einschließlich Approximationsverhältnis und Stichprobenkomplexität
  3. Algorithmusische Innovation: Geschickte Anwendung von kontinuierlichem Greedy und zufälligem Runden auf Multi-Produkt-Szenarien
  4. Umfassende Experimente: Ausreichende experimentelle Validierung auf echten Datensätzen

Schwächen

  1. Skalierungsbeschränkungen: Exponentielle Komplexität des RA-Algorithmus begrenzt Anwendung bei großen Problemen
  2. Einfache Baseline-Methoden: Vergleichsmethoden sind relativ einfach; Vergleich mit fortgeschritteneren Methoden fehlt
  3. Unzureichende Parameterempfindlichkeitsanalyse: Analyse der Empfindlichkeit gegenüber Schlüsselparametern (wie Distanzschwelle λ) nicht ausreichend
  4. Praktische Einschränkungen: Unzureichende Berücksichtigung von Zeiteinschränkungen und Wettbewerbsfaktoren in der praktischen Werbeplatzierung

Einfluss

  1. Akademischer Beitrag: Bietet erste systematische Forschung zum Multi-Produkt-Einflussmaximierungsproblem
  2. Praktischer Wert: Direkt anwendbar auf Außenwerbung, digitale Beschilderung und andere Szenarien
  3. Theoretische Bedeutung: Erweitert Anwendungsbereich der Submodular-Optimierungstheorie
  4. Reproduzierbarkeit: Bietet detaillierte Algorithmusbeschreibung und experimentelle Einrichtung

Anwendungsszenarien

  1. Außenwerbenetze: Multi-Produkt-Platzierungsoptimierung in traditionellen Plakatwerbungsnetzen
  2. Digitale Beschilderungssysteme: Werbeplatzierung auf digitalen Displays in Einkaufszentren, Flughäfen usw.
  3. Verkehrswerbung: Werbeplatzverteilung auf Bussen, U-Bahnen und anderen Verkehrsmitteln
  4. Online-Werbung: Erweiterbar auf Multi-Produkt-Gebote und Zuweisungsprobleme in Online-Werbung

Referenzen

Das Papier zitiert 22 verwandte Referenzen, hauptsächlich einschließlich:

  • Klassische Arbeiten zur Einflussmaximierung (Kempe et al., 2003)
  • Theoretische Grundlagen der Submodular-Optimierung (Calinescu et al., 2007; Vondrák, 2007)
  • Multi-Submodular-Überdeckungsproblem (Chekuri et al., 2022)
  • Verwandte Forschung zu Plakatwerbung (Zhang et al., 2020, 2021)
  • Wahrscheinlichkeitsungleichungstheorie (Hoeffding, 1963)

Dieses Papier leistet wichtige Beiträge auf theoretischer und praktischer Ebene und bietet systematische Lösungen für das Multi-Produkt-Einflussmaximierungsproblem. Trotz einiger Einschränkungen machen seine Innovativität und praktischer Wert es zu einem wichtigen Fortschritt in diesem Bereich.