Maximización de Influencia Multiproducto en Publicidad en Vallas Publicitarias

Información Básica

• ID del Artículo: 2510.09050
• Título: Multi-product Influence Maximization in Billboard Advertisement
• Autores: Dildar Ali (IIT Jammu), Rajibul Islam (Gandhi Institute for Technological Advancement), Suman Banerjee (IIT Jammu)
• Clasificación: cs.DS (Estructuras de Datos y Algoritmos), cs.DB (Bases de Datos)
• Fecha de Publicación: 10 de octubre de 2025 (preimpresión en arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2510.09050

Resumen

Las vallas publicitarias exteriores se han convertido en una tecnología publicitaria efectiva, cuyo objetivo es seleccionar un número limitado de franjas horarias y reproducir contenido publicitario en ellas, esperando ser observadas por muchas personas e influir efectivamente en la actitud de una cantidad considerable de personas hacia la marca. Este artículo investiga una variante del problema: las empresas comerciales desean promocionar múltiples productos, cada uno con requisitos de influencia específicos. Se estudiaron dos variantes del problema: la primera tiene como objetivo seleccionar k franjas horarias de modo que se satisfagan los requisitos de influencia correspondientes para cada producto; en la segunda variante, dados ℓ enteros k₁, k₂, ..., k_ℓ, el objetivo es encontrar ℓ conjuntos de franjas horarias S₁, S₂, ..., S_ℓ que sean mutuamente disjuntos y satisfagan los requisitos de influencia de cada producto.

Antecedentes y Motivación de la Investigación

Contexto del Problema

1. Importancia de la Publicidad Exterior: Las empresas comerciales típicamente dedican el 7-10% de sus ingresos totales a publicidad, siendo las vallas publicitarias exteriores un método efectivo por sus garantías de retorno de inversión y facilidad de uso
2. Limitaciones de Problemas Tradicionales: La investigación existente se enfoca principalmente en la maximización de influencia de un único anunciante o la minimización del arrepentimiento entre múltiples anunciantes
3. Necesidades Prácticas: Las empresas comerciales típicamente necesitan promocionar simultáneamente múltiples productos heterogéneos, cada uno dirigido a diferentes grupos de clientes

Motivación de la Investigación

• Necesidades Prácticas: En la realidad, los anunciantes necesitan satisfacer diferentes requisitos de influencia para múltiples productos dentro de un presupuesto unificado
• Vacío Teórico: La literatura existente carece de investigación sobre el problema de selección de franjas horarias en vallas publicitarias multiproducto
• Desafíos Técnicos: Se requiere minimizar el costo total mientras se satisfacen las restricciones de influencia de cada producto

Contribuciones Principales

1. Extensión del Problema: Se extiende el problema de selección de franjas horarias de influencia al escenario de publicidad multiproducto, investigando dos variantes relacionadas del problema
2. Modelado Teórico: Se modela la primera variante como un problema de cobertura multisubmodular, y la segunda variante como una versión generalizada
3. Diseño de Algoritmos:
   • Se adopta un algoritmo de aproximación de doble criterio para la primera variante
   • Se propone un algoritmo de aproximación basado en muestreo para la segunda variante
4. Optimización de Eficiencia: Se desarrollan soluciones heurísticas eficientes para abordar problemas de escalabilidad
5. Verificación Experimental: Se realizaron experimentos extensivos en conjuntos de datos de trayectorias reales y vallas publicitarias

Explicación Detallada de Métodos

Definición de Tareas

Entrada:

• Base de datos de trayectorias D: contiene información de ubicación-tiempo de usuarios e intereses en productos
• Base de datos de vallas publicitarias B: contiene ubicación de vallas, franjas horarias e información de costos
• Función de costo c: BS → R⁺
• Conjunto de productos P = {1,2,...,ℓ}

Dos Variantes del Problema:

1. Problema Común de Selección de Franjas Horarias Multiproducto:
   • Seleccionar un único conjunto de franjas horarias S ⊆ BS
   • Minimizar el costo total ∑_{s∈S} c(s)
   • Satisfacer restricciones: ∀j ∈ ℓ, I_j(S) ≥ k_j
2. Problema Disjunto de Selección de Franjas Horarias Multiproducto:
   • Seleccionar ℓ conjuntos de franjas horarias mutuamente disjuntos S₁, S₂, ..., S_ℓ
   • Satisfacer: |S_j| ≤ k_j, S_i ∩ S_j = ∅ (i≠j), I_j(S_j) ≥ σ_j

Técnicas Principales

1. Modelado de Función de Influencia

La función de influencia del producto j se define como:

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

donde U_j es el conjunto de usuarios interesados en el producto j, y Pr(s_j, u_i) es la probabilidad de influencia de la franja horaria s_j en el usuario u_i.

2. Propiedad Submodular

La función de influencia posee la propiedad submodular, satisfaciendo el efecto de rendimientos marginales decrecientes:

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

Arquitectura de Algoritmos

Algoritmo 1: Algoritmo de Aproximación de Doble Criterio para Selección de Franjas Horarias Comunes

1. Normalización: Normalizar la función de influencia de cada producto de modo que I_j(BS) = 1
2. Codicioso Continuo: Utilizar extensión multilineal para resolver soluciones fraccionarias en el poliedro matroide
3. Redondeo Aleatorio: Muestrear ℓ = ⌈log_{1/(1-ε)}(r)⌉ subconjuntos aleatorios
4. Paso de Reparación: Agregar codiciosamente franjas horarias para productos que no satisfacen restricciones

Algoritmo 2: Algoritmo de Muestreo para Selección de Franjas Horarias Disjuntas

1. Muestreo de Permutaciones: Muestrear aleatoriamente permutaciones de asignaciones producto-franja horaria
2. Asignación Codicioso: Seleccionar codiciosamente franjas horarias para cada producto en orden de permutación
3. Verificación de Viabilidad: Verificar si se satisfacen todas las restricciones
4. Selección Óptima: Devolver la solución viable con costo mínimo

Puntos de Innovación Técnica

1. Aplicación de Extensión Multilineal: Aplicar técnicas de extensión continua de funciones submodulares al escenario multiproducto
2. Análisis de Complejidad de Muestreo: Utilizar la desigualdad de Hoeffding para analizar la complejidad de muestreo del algoritmo
3. Aproximación de Doble Criterio: Proporcionar garantías de aproximación de costo mientras se satisfacen restricciones de influencia

Configuración Experimental

Conjuntos de Datos

1. Nueva York (NYC):
   • 227,428 registros de check-in (abril de 2012 - febrero de 2013)
   • 1,083 usuarios únicos
   • 716 vallas publicitarias, 1,031,040 franjas horarias
2. Los Ángeles (LA):
   • 74,170 registros de check-in, cubriendo 15 calles
   • 2,000 usuarios únicos
   • 1,483 vallas publicitarias, 2,135,520 franjas horarias

Métricas de Evaluación

• Influencia: Influencia total alcanzada para cada producto
• Número de Franjas Horarias: Número total de franjas horarias asignadas a cada producto
• Tiempo de Cálculo: Tiempo de ejecución del algoritmo
• Costo: Costo total de selección de franjas horarias

Métodos de Comparación

1. Asignación Aleatoria (RA): Seleccionar aleatoriamente franjas horarias para asignar a productos
2. Asignación Top-k: Ordenar por valor de influencia, asignando prioritariamente franjas horarias de alta influencia

Parámetros Clave

• Relación de Demanda-Oferta α: Proporción de demanda de influencia global respecto a oferta total (40%-120%)
• Relación de Demanda Individual β: Proporción de demanda individual promedio respecto a oferta total (1%-20%)
• Número de Productos |P|: 5, 10, 20, 50, 100
• Parámetro de Distancia λ: 25m-150m
• Parámetro de Aproximación ε: 0.01-0.2

Resultados Experimentales

Resultados Principales

Rendimiento de Influencia

• Conjunto de Datos NYC: El método BCA supera a los métodos de línea base en 20-25%, con el método RA mostrando el mejor rendimiento
• Conjunto de Datos LA: El método BCA supera a los métodos de línea base en 8-10%
• Cuando α≥100% y β≥10%, la demanda excede la oferta, el método BCA supera a la línea base pero el método RA no tiene solución viable

Eficiencia de Asignación de Franjas Horarias

• A medida que α y β aumentan, el número de franjas horarias asignadas a cada producto aumenta
• El método Top-k asigna menos franjas horarias que el método Aleatorio
• El método BCA asigna más franjas horarias que los métodos RA y de línea base (porque necesita satisfacer los requisitos de todos los productos)

Complejidad Computacional

• Complejidad Temporal:
  • Algoritmo BCA: O(n²ℓ/ε + nℓ)
  • Algoritmo RA: O(|X|·ℓ·B_max/c_min·n·t)
• El método RA tiene el tiempo de cálculo más largo (necesita considerar muchas permutaciones)
• El tiempo del método BCA es moderado, creciendo lentamente con α y β

Eficiencia de Costos

• El método RA muestra el mejor rendimiento en términos de costo, utilizando el costo mínimo para satisfacer todos los requisitos de productos
• A medida que aumentan los requisitos, el costo de asignación de todos los métodos aumenta

Garantías Teóricas

Relación de Aproximación del Algoritmo BCA

Teorema: Sea r la dispersidad (la máxima contribución de cualquier franja horaria a las funciones), ε > 0. El algoritmo BCA devuelve con alta probabilidad un conjunto S que satisface:

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

Complejidad de Muestreo

Teorema: Para cualquier ε,δ ∈ (0,1), si el tamaño de muestra ≥ ln(2/δ)·c(BS)²/(2ε²·(W_A)²), entonces la probabilidad de que el error computacional sea menor que ε es al menos (1-δ).

Trabajo Relacionado

Selección de Franjas Horarias de Influencia

• Métodos de Gráficos Submodulares: Métodos basados en gráficos submodulares podados
• Marco de Ramificación y Acotación: Marco de algoritmo exacto
• Soluciones Codiciosas: Algoritmos codiciosos basados en ganancia marginal
• Métodos de Coevolución Cooperativa: Método de Coevolución Cooperativa propuesto por Wang et al.

Minimización de Arrepentimiento

• Métodos de Búsqueda Local: Solución de búsqueda local de Zhang et al.
• Restricciones Regionales: Investigación de minimización de arrepentimiento bajo restricciones de influencia regional de Ali et al.

Fundamentos Teóricos

• Problema de Cobertura Multisubmodular: Algoritmo de aproximación de doble criterio aleatorio de Chekuri et al.
• Algoritmo Codicioso Continuo: Técnicas de extensión continua para funciones submodulares monótonas

Conclusiones y Discusión

Conclusiones Principales

1. Modelado del Problema: Se modeló exitosamente el problema de vallas publicitarias multiproducto como un problema de cobertura multisubmodular y su generalización
2. Efectividad del Algoritmo: Los algoritmos propuestos muestran buen rendimiento tanto teórica como prácticamente
3. Valor Práctico: Los métodos son aplicables a cualquier escenario de publicidad exterior multiproducto

Limitaciones

1. Complejidad Computacional: La complejidad temporal exponencial del algoritmo RA limita su aplicación a gran escala
2. Condiciones de Supuesto: Se asume que la función de influencia posee la propiedad submodular, que podría no satisfacerse completamente en la práctica
3. Dependencia de Datos: Requiere datos de trayectoria precisos e información de preferencias de productos de usuarios
4. Modelo Estático: No considera cambios en demanda y oferta en entornos dinámicos

Direcciones Futuras

1. Optimización Dinámica: Considerar requisitos de influencia variables en el tiempo y comportamiento de usuarios
2. Algoritmos en Línea: Desarrollar algoritmos de optimización en línea para procesar flujos de datos en tiempo real
3. Integración de Aprendizaje Automático: Combinar aprendizaje profundo para predecir intereses de usuarios e influencia
4. Optimización Multiobjetivo: Considerar simultáneamente múltiples objetivos como costo, cobertura y equidad

Evaluación Profunda

Fortalezas

1. Importancia del Problema: Resuelve un problema importante en entornos comerciales reales con valor de aplicación claro
2. Rigor Teórico: Proporciona análisis teórico completo incluyendo relaciones de aproximación y complejidad de muestreo
3. Innovación Algorítmica: Aplica ingeniosamente técnicas de codicioso continuo y redondeo aleatorio al escenario multiproducto
4. Verificación Experimental Completa: Realiza verificación experimental suficiente en conjuntos de datos reales

Deficiencias

1. Limitaciones de Escalabilidad: La complejidad exponencial del algoritmo RA limita su aplicación en problemas a gran escala
2. Métodos de Línea Base Simples: Los métodos de línea base para comparación son relativamente simples, careciendo de comparación con métodos más avanzados
3. Análisis de Sensibilidad Insuficiente: El análisis de sensibilidad respecto a parámetros clave (como el umbral de distancia λ) no es suficientemente profundo
4. Restricciones Prácticas: No considera suficientemente restricciones de tiempo y factores competitivos en la colocación de anuncios reales

Impacto

1. Contribución Académica: Proporciona el primer estudio sistemático del problema de maximización de influencia multiproducto
2. Valor Práctico: Puede aplicarse directamente a publicidad exterior, señalización digital y otros escenarios
3. Significado Teórico: Extiende el alcance de la teoría de optimización submodular en aplicaciones prácticas
4. Reproducibilidad: Proporciona descripciones detalladas de algoritmos y configuración experimental

Escenarios Aplicables

1. Redes de Publicidad Exterior: Optimización de colocación multiproducto en redes de vallas publicitarias tradicionales
2. Sistemas de Señalización Digital: Asignación de anuncios en pantallas digitales en centros comerciales, aeropuertos, etc.
3. Publicidad en Transporte: Asignación de espacios publicitarios en autobuses, metros y otros vehículos de transporte
4. Publicidad en Línea: Extensible a problemas de pujas y asignación multiproducto en publicidad en línea

Referencias

El artículo cita 22 referencias relacionadas, incluyendo principalmente:

• Trabajos clásicos en maximización de influencia (Kempe et al., 2003)
• Fundamentos teóricos de optimización submodular (Calinescu et al., 2007; Vondrák, 2007)
• Problema de cobertura multisubmodular (Chekuri et al., 2022)
• Investigación relacionada con publicidad en vallas publicitarias (Zhang et al., 2020, 2021)
• Teoría de desigualdades probabilísticas (Hoeffding, 1963)

Este artículo realiza contribuciones importantes tanto en niveles teóricos como prácticos, proporcionando una solución sistemática al problema de maximización de influencia multiproducto. Aunque existen algunas limitaciones, su innovación y valor práctico lo convierten en un progreso importante en este campo.