Massimizzazione dell'Influenza Multi-Prodotto nella Pubblicità su Cartelloni

Informazioni Fondamentali

• ID Articolo: 2510.09050
• Titolo: Multi-product Influence Maximization in Billboard Advertisement
• Autori: Dildar Ali (IIT Jammu), Rajibul Islam (Gandhi Institute for Technological Advancement), Suman Banerjee (IIT Jammu)
• Classificazione: cs.DS (Strutture Dati e Algoritmi), cs.DB (Banche Dati)
• Data di Pubblicazione: 10 ottobre 2025 (preprint arXiv)
• Link Articolo: https://arxiv.org/abs/2510.09050

Riassunto

I cartelloni pubblicitari esterni sono diventati una tecnologia pubblicitaria efficace, con l'obiettivo di selezionare un numero limitato di fasce orarie e trasmettere contenuti pubblicitari in esse, sperando di essere osservati da molte persone e influenzare efficacemente l'atteggiamento di un numero considerevole di persone verso i marchi. Questo articolo studia una variante del problema: le aziende commerciali desiderano promuovere più prodotti, ciascuno con requisiti di influenza specifici. Sono state studiate due varianti del problema: la prima variante ha l'obiettivo di selezionare k fasce orarie in modo che i corrispondenti requisiti di influenza per ogni prodotto siano soddisfatti; nella seconda variante, dati ℓ interi k₁,k₂,...,k_ℓ, l'obiettivo è trovare ℓ insiemi di fasce orarie S₁,S₂,...,S_ℓ, che soddisfino la condizione di mutua disgiunzione e che i requisiti di influenza per ogni prodotto siano soddisfatti.

Contesto di Ricerca e Motivazione

Contesto del Problema

1. Importanza della Pubblicità Esterna: Le aziende commerciali generalmente destinano il 7-10% dei ricavi totali alla pubblicità; i cartelloni pubblicitari esterni sono un metodo efficace grazie alle garanzie di ritorno sull'investimento e alla facilità d'uso
2. Limitazioni dei Problemi Tradizionali: La ricerca esistente si concentra principalmente sulla massimizzazione dell'influenza di un singolo inserzionista o sulla minimizzazione del rammarico tra più inserzionisti
3. Esigenze Pratiche: Le aziende commerciali generalmente necessitano di promuovere contemporaneamente più prodotti eterogenei, ciascuno rivolto a diversi segmenti di clientela

Motivazione della Ricerca

• Esigenze Pratiche: Nella realtà, gli inserzionisti devono soddisfare diversi requisiti di influenza per più prodotti entro un budget unificato
• Lacuna Teorica: La letteratura esistente manca di ricerche specifiche sul problema della selezione delle fasce orarie per cartelloni pubblicitari multi-prodotto
• Sfide Tecniche: È necessario minimizzare il costo totale soddisfacendo contemporaneamente i vincoli di influenza per ogni prodotto

Contributi Fondamentali

1. Estensione del Problema: Estensione del problema di selezione delle fasce orarie di influenza a scenari pubblicitari multi-prodotto, studiando due varianti correlate del problema
2. Modellazione Teorica: Modellazione della prima variante come problema di copertura multi-submodulare e della seconda variante come versione generalizzata
3. Progettazione di Algoritmi:
   • Adozione di un algoritmo di approssimazione a doppio criterio per la prima variante
   • Proposta di un algoritmo di approssimazione basato su campionamento per la seconda variante
4. Ottimizzazione dell'Efficienza: Sviluppo di soluzioni euristiche efficienti per affrontare problemi di scalabilità
5. Verifica Sperimentale: Esperimenti estesi su dataset di tracce reali e dati di cartelloni pubblicitari

Spiegazione Dettagliata dei Metodi

Definizione del Compito

Input:

• Database di tracce D: contiene informazioni sulla posizione-tempo dell'utente e interessi nei prodotti
• Database di cartelloni B: contiene posizione dei cartelloni, fasce orarie e informazioni sui costi
• Funzione di costo c: BS → R⁺
• Insieme di prodotti P = {1,2,...,ℓ}

Due Varianti del Problema:

1. Problema di Selezione di Fasce Orarie Multi-Prodotto Comune:
   • Selezionare un singolo insieme di fasce orarie S ⊆ BS
   • Minimizzare il costo totale ∑_{s∈S} c(s)
   • Soddisfare il vincolo: ∀j ∈ ℓ, I_j(S) ≥ k_j
2. Problema di Selezione di Fasce Orarie Multi-Prodotto Disgiunto:
   • Selezionare ℓ insiemi di fasce orarie mutuamente disgiunti S₁,S₂,...,S_ℓ
   • Soddisfare: |S_j| ≤ k_j, S_i ∩ S_j = ∅ (i≠j), I_j(S_j) ≥ σ_j

Tecniche Fondamentali

1. Modellazione della Funzione di Influenza

La funzione di influenza per il prodotto j è definita come:

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

dove U_j è l'insieme di utenti interessati al prodotto j, e Pr(s_j, u_i) è la probabilità di influenza della fascia oraria s_j sull'utente u_i.

2. Proprietà di Submodularità

La funzione di influenza possiede la proprietà di submodularità, soddisfacendo l'effetto di rendimento marginale decrescente:

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

Architettura dell'Algoritmo

Algoritmo 1: Algoritmo di Approssimazione a Doppio Criterio per la Selezione di Fasce Orarie Comuni

1. Normalizzazione: Normalizzazione della funzione di influenza di ogni prodotto in modo che I_j(BS) = 1
2. Greedy Continuo: Utilizzo dell'estensione multilineare per risolvere la soluzione frazionaria sul poliedro matroide
3. Arrotondamento Casuale: Campionamento di ℓ = ⌈log_{1/(1-ε)}(r)⌉ sottoinsiemi casuali
4. Fase di Riparazione: Aggiunta greedy di fasce orarie per i prodotti che non soddisfano i vincoli

Algoritmo 2: Algoritmo di Campionamento per la Selezione di Fasce Orarie Disgiunte

1. Campionamento di Permutazioni: Campionamento casuale di permutazioni di assegnazione prodotto-fascia oraria
2. Assegnazione Greedy: Selezione greedy di fasce orarie per ogni prodotto secondo l'ordine di permutazione
3. Verifica di Fattibilità: Verifica del soddisfacimento di tutti i vincoli
4. Selezione Ottimale: Restituzione della soluzione fattibile con costo minimo

Punti di Innovazione Tecnica

1. Applicazione dell'Estensione Multilineare: Applicazione della tecnica di estensione continua di funzioni submodulari a scenari multi-prodotto
2. Analisi della Complessità di Campionamento: Utilizzo della disuguaglianza di Hoeffding per analizzare la complessità campionaria dell'algoritmo di campionamento
3. Approssimazione a Doppio Criterio: Fornitura di garanzie di approssimazione del costo soddisfacendo contemporaneamente i vincoli di influenza

Configurazione Sperimentale

Dataset

1. New York City (NYC):
   • 227.428 registrazioni di check-in (aprile 2012 - febbraio 2013)
   • 1.083 utenti unici
   • 716 cartelloni pubblicitari, 1.031.040 fasce orarie
2. Los Angeles (LA):
   • 74.170 registrazioni di check-in, coprendo 15 strade
   • 2.000 utenti unici
   • 1.483 cartelloni pubblicitari, 2.135.520 fasce orarie

Metriche di Valutazione

• Influenza: Influenza totale raggiunta per ogni prodotto
• Numero di Fasce Orarie: Numero totale di fasce orarie assegnate ai prodotti
• Tempo di Calcolo: Tempo di esecuzione dell'algoritmo
• Costo: Costo totale della selezione delle fasce orarie

Metodi di Confronto

1. Random Allocation (RA): Selezione casuale di fasce orarie assegnate ai prodotti
2. Top-k Allocation: Ordinamento per valore di influenza, assegnazione prioritaria di fasce orarie ad alta influenza

Parametri Chiave

• Rapporto di Domanda-Offerta α: Rapporto tra domanda di influenza globale e offerta totale (40%-120%)
• Rapporto di Domanda Individuale β: Rapporto tra domanda individuale media e offerta totale (1%-20%)
• Numero di Prodotti |P|: 5, 10, 20, 50, 100
• Parametro di Distanza λ: 25m-150m
• Parametro di Approssimazione ε: 0.01-0.2

Risultati Sperimentali

Risultati Principali

Prestazioni di Influenza

• Dataset NYC: Il metodo BCA supera i metodi di base del 20-25%, il metodo RA mostra le migliori prestazioni
• Dataset LA: Il metodo BCA supera i metodi di base dell'8-10%
• Quando α≥100% e β≥10%, la domanda supera l'offerta, il metodo BCA supera la linea di base ma il metodo RA non ha soluzioni fattibili

Efficienza di Allocazione delle Fasce Orarie

• Con l'aumento di α e β, il numero di fasce orarie allocate a ogni prodotto aumenta
• Il metodo Top-k alloca meno fasce orarie rispetto al metodo Random
• Il metodo BCA alloca più fasce orarie rispetto ai metodi RA e di base (perché deve soddisfare i requisiti di tutti i prodotti)

Complessità Computazionale

• Complessità Temporale:
  • Algoritmo BCA: O(n²ℓ/ε + nℓ)
  • Algoritmo RA: O(|X|·ℓ·B_max/c_min·n·t)
• Il metodo RA ha il tempo di calcolo più lungo (deve considerare un gran numero di permutazioni)
• Il tempo del metodo BCA è moderato, crescendo lentamente con α e β

Efficienza dei Costi

• Il metodo RA mostra le migliori prestazioni in termini di costo, utilizzando il costo minimo per soddisfare i requisiti di tutti i prodotti
• Con l'aumento della domanda, il costo di allocazione di tutti i metodi aumenta

Garanzie Teoriche

Rapporto di Approssimazione dell'Algoritmo BCA

Teorema: Sia r il grado di sparsità (il massimo numero di funzioni a cui una singola fascia oraria può contribuire), ε > 0. L'algoritmo BCA restituisce con alta probabilità un insieme S che soddisfa:

• Per tutti j ∈ ℓ: I_j(S) ≥ (1 - 1/e - ε)·k_j
• Costo atteso: Ec(S) = O(1/ε·log r)·OPT

Complessità di Campionamento

Teorema: Per qualsiasi ε,δ ∈ (0,1), se la dimensione del campione ≥ ln(2/δ)·c(BS)²/(2ε²·(W_A)²), allora la probabilità che l'errore di calcolo sia inferiore a ε è almeno (1-δ).

Lavori Correlati

Selezione di Fasce Orarie di Influenza

• Metodo di Grafo Submodulare: Metodi basati su grafo submodulare potato
• Framework di Branch and Bound: Framework di algoritmo esatto
• Soluzione Greedy: Algoritmo greedy basato su rendimento marginale
• Metodo di Co-evoluzione Cooperativa: Metodo Co-operative Co-Evolutionary proposto da Wang et al.

Minimizzazione del Rammarico

• Metodo di Ricerca Locale: Soluzione di ricerca locale di Zhang et al.
• Vincoli Regionali: Ricerca sulla minimizzazione del rammarico con vincoli di influenza regionale di Ali et al.

Fondamenti Teorici

• Problema di Copertura Multi-Submodulare: Algoritmo di approssimazione a doppio criterio casuale di Chekuri et al.
• Algoritmo Greedy Continuo: Tecnica di estensione continua di funzioni submodulari monotone

Conclusioni e Discussione

Conclusioni Principali

1. Modellazione del Problema: Modellazione riuscita del problema dei cartelloni pubblicitari multi-prodotto come problema di copertura multi-submodulare e sua generalizzazione
2. Efficacia dell'Algoritmo: Gli algoritmi proposti mostrano buone prestazioni sia teoricamente che praticamente
3. Valore Pratico: Il metodo è applicabile a qualsiasi scenario di pubblicità esterna multi-prodotto

Limitazioni

1. Complessità Computazionale: La complessità temporale esponenziale dell'algoritmo RA limita l'applicazione su larga scala
2. Condizioni di Assunzione: Si assume che la funzione di influenza possieda la proprietà di submodularità, che potrebbe non essere completamente soddisfatta nella pratica
3. Dipendenza dai Dati: Richiede dati di traccia accurati e informazioni sulle preferenze dei prodotti degli utenti
4. Modello Statico: Non considera i cambiamenti della domanda e dell'offerta in ambienti dinamici

Direzioni Future

1. Ottimizzazione Dinamica: Considerazione dei requisiti di influenza variabili nel tempo e del comportamento degli utenti
2. Algoritmi Online: Sviluppo di algoritmi di ottimizzazione online per l'elaborazione di flussi di dati in tempo reale
3. Integrazione di Apprendimento Automatico: Combinazione di apprendimento profondo per prevedere gli interessi degli utenti e l'influenza
4. Ottimizzazione Multi-Obiettivo: Considerazione simultanea di più obiettivi come costo, copertura e equità

Valutazione Approfondita

Punti di Forza

1. Importanza del Problema: Risolve un problema importante nell'ambiente commerciale reale, con chiaro valore applicativo
2. Rigore Teorico: Fornisce un'analisi teorica completa, inclusi rapporti di approssimazione e complessità di campionamento
3. Innovazione Algoritmica: Applicazione ingegnosa di tecniche di greedy continuo e arrotondamento casuale a scenari multi-prodotto
4. Esperimenti Completi: Verifica sperimentale sufficiente su dataset reali

Insufficienze

1. Limitazioni di Scalabilità: La complessità esponenziale dell'algoritmo RA limita l'applicazione su problemi su larga scala
2. Metodi di Base Semplici: I metodi di base per il confronto sono relativamente semplici, mancano confronti con metodi più avanzati
3. Analisi di Sensibilità ai Parametri: L'analisi della sensibilità ai parametri chiave (come la soglia di distanza λ) non è sufficientemente approfondita
4. Vincoli Pratici: Non considera sufficientemente i vincoli temporali e i fattori di competizione nell'effettivo posizionamento pubblicitario

Impatto

1. Contributo Accademico: Fornisce il primo studio sistematico del problema di massimizzazione dell'influenza multi-prodotto
2. Valore Pratico: Può essere direttamente applicato a pubblicità esterna, segnaletica digitale e altri scenari
3. Significato Teorico: Estende l'ambito di applicazione della teoria dell'ottimizzazione submodulare
4. Riproducibilità: Fornisce descrizioni dettagliate degli algoritmi e configurazioni sperimentali

Scenari Applicabili

1. Reti Pubblicitarie Esterne: Ottimizzazione del posizionamento multi-prodotto su reti di cartelloni pubblicitari tradizionali
2. Sistemi di Segnaletica Digitale: Allocazione di annunci su schermi digitali in centri commerciali, aeroporti e altri luoghi
3. Pubblicità nei Trasporti: Allocazione di spazi pubblicitari su autobus, metropolitane e altri mezzi di trasporto
4. Pubblicità Online: Estensione a problemi di asta e allocazione di annunci online multi-prodotto

Bibliografia

L'articolo cita 22 riferimenti correlati, principalmente includenti:

• Lavori classici sulla massimizzazione dell'influenza (Kempe et al., 2003)
• Fondamenti teorici dell'ottimizzazione submodulare (Calinescu et al., 2007; Vondrák, 2007)
• Problema di copertura multi-submodulare (Chekuri et al., 2022)
• Ricerche correlate sulla pubblicità su cartelloni (Zhang et al., 2020, 2021)
• Teoria delle disuguaglianze probabilistiche (Hoeffding, 1963)

Questo articolo fornisce contributi significativi sia a livello teorico che pratico, offrendo una soluzione sistematica al problema di massimizzazione dell'influenza multi-prodotto. Nonostante alcune limitazioni, la sua innovatività e valore pratico lo rendono un progresso importante in questo campo di ricerca.