Максимизация влияния многопродуктовой рекламы на билбордах

Основная информация

• ID статьи: 2510.09050
• Название: Multi-product Influence Maximization in Billboard Advertisement
• Авторы: Dildar Ali (IIT Jammu), Rajibul Islam (Gandhi Institute for Technological Advancement), Suman Banerjee (IIT Jammu)
• Классификация: cs.DS (Структуры данных и алгоритмы), cs.DB (Базы данных)
• Дата публикации: 10 октября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2510.09050

Аннотация

Наружная реклама на билбордах стала эффективной технологией уличной рекламы, целью которой является выбор ограниченного количества временных слотов для трансляции рекламного контента, рассчитывая на наблюдение большого числа людей и эффективное влияние на отношение значительного количества потребителей к бренду. В данной работе исследуется вариант задачи, при котором коммерческие компании желают продвигать несколько продуктов, каждый из которых имеет требования по влиянию. Изучены два варианта задачи: первый вариант ставит целью выбрать k временных слотов таким образом, чтобы соответствующие требования по влиянию для каждого продукта были удовлетворены; во втором варианте, при наличии ℓ целых чисел k₁,k₂,...,k_ℓ, целью является поиск ℓ непересекающихся множеств временных слотов S₁,S₂,...,S_ℓ, удовлетворяющих условиям взаимной непересекаемости и выполнения требований по влиянию для каждого продукта.

Исследовательский контекст и мотивация

Предпосылки задачи

1. Значимость наружной рекламы: Коммерческие компании обычно выделяют 7-10% от общих доходов на рекламу; наружные билборды являются эффективным методом благодаря гарантированной окупаемости инвестиций и простоте использования
2. Ограничения традиционных подходов: Существующие исследования сосредоточены главным образом на максимизации влияния одного рекламодателя или минимизации сожаления между несколькими рекламодателями
3. Практические требования: Коммерческие компании обычно нуждаются в одновременном продвижении нескольких гетерогенных продуктов, каждый из которых ориентирован на различные группы потребителей

Научная мотивация

• Практическая необходимость: В реальности рекламодатели должны удовлетворять различные требования по влиянию нескольких продуктов в рамках единого бюджета
• Теоретический пробел: В существующей литературе отсутствуют исследования, посвящённые задаче выбора временных слотов для многопродуктовой рекламы на билбордах
• Технические вызовы: Необходимо минимизировать общие затраты при одновременном удовлетворении ограничений по влиянию для каждого продукта

Основные вклады

1. Расширение задачи: Расширение задачи выбора временных слотов влияния на сценарий многопродуктовой рекламы на билбордах с исследованием двух связанных вариантов задачи
2. Теоретическое моделирование: Моделирование первого варианта как задачи многосубмодульного покрытия, второго варианта как обобщённой версии
3. Разработка алгоритмов:
   • Применение двукритериального приближённого алгоритма для первого варианта
   • Предложение алгоритма на основе выборки для второго варианта
4. Оптимизация эффективности: Разработка эффективных эвристических решений для решения проблем масштабируемости
5. Экспериментальная проверка: Проведение обширных экспериментов на реальных наборах данных траекторий и билбордов

Подробное описание методов

Определение задачи

Входные данные:

• База данных траекторий D: содержит информацию о местоположении-времени пользователей и интересах к продуктам
• База данных билбордов B: содержит информацию о местоположении билбордов, временных слотах и стоимости
• Функция стоимости c: BS → R⁺
• Множество продуктов P = {1,2,...,ℓ}

Два варианта задачи:

1. Задача выбора общего многопродуктового временного слота:
   • Выбрать единственное множество слотов S ⊆ BS
   • Минимизировать общую стоимость ∑_{s∈S} c(s)
   • Удовлетворить ограничение: ∀j ∈ ℓ, I_j(S) ≥ k_j
2. Задача выбора непересекающихся многопродуктовых временных слотов:
   • Выбрать ℓ непересекающихся множеств временных слотов S₁,S₂,...,S_ℓ
   • Удовлетворить: |S_j| ≤ k_j, S_i ∩ S_j = ∅ (i≠j), I_j(S_j) ≥ σ_j

Основные технологии

1. Моделирование функции влияния

Функция влияния для продукта j определяется как:

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

где U_j — множество пользователей, заинтересованных в продукте j, Pr(s_j, u_i) — вероятность влияния временного слота s_j на пользователя u_i.

2. Свойство субмодульности

Функция влияния обладает свойством субмодульности, удовлетворяя эффекту убывающей предельной полезности:

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

Архитектура алгоритма

Алгоритм 1: Двукритериальный приближённый алгоритм для выбора общего слота

1. Нормализация: Нормализация функции влияния каждого продукта таким образом, чтобы I_j(BS) = 1
2. Непрерывная жадность: Использование многолинейного расширения для решения дробного решения на матроидном многограннике
3. Случайное округление: Выборка ℓ = ⌈log_{1/(1-ε)}(r)⌉ случайных подмножеств
4. Шаг восстановления: Жадное добавление временных слотов для продуктов, не удовлетворяющих ограничениям

Алгоритм 2: Алгоритм выборки для выбора непересекающихся слотов

1. Выборка перестановок: Случайная выборка перестановок распределения продукт-слот
2. Жадное распределение: Жадный выбор временных слотов для каждого продукта в порядке перестановки
3. Проверка допустимости: Проверка удовлетворения всех ограничений
4. Оптимальный выбор: Возврат допустимого решения с минимальной стоимостью

Технические инновации

1. Применение многолинейного расширения: Применение техники непрерывного расширения субмодульных функций к многопродуктовому сценарию
2. Анализ сложности выборки: Использование неравенства Хёффдинга для анализа сложности выборки алгоритма выборки
3. Двукритериальное приближение: Обеспечение гарантий приближения стоимости при удовлетворении ограничений влияния

Экспериментальная установка

Наборы данных

1. Нью-Йорк (NYC):
   • 227 428 записей регистрации (апрель 2012 г. — февраль 2013 г.)
   • 1 083 уникальных пользователя
   • 716 билбордов, 1 031 040 временных слотов
2. Лос-Анджелес (LA):
   • 74 170 записей регистрации, охватывающих 15 улиц
   • 2 000 уникальных пользователей
   • 1 483 билборда, 2 135 520 временных слотов

Метрики оценки

• Влияние: Общее влияние, достигнутое каждым продуктом
• Количество слотов: Общее количество временных слотов, выделенных продуктам
• Время вычисления: Время выполнения алгоритма
• Стоимость: Общая стоимость выбора временных слотов

Методы сравнения

1. Random Allocation (RA): Случайный выбор распределения временных слотов продуктам
2. Top-k Allocation: Приоритетное распределение временных слотов с высоким значением влияния

Ключевые параметры

• Коэффициент спроса-предложения α: Отношение глобального требования влияния к общему предложению (40%-120%)
• Коэффициент индивидуального спроса β: Отношение среднего индивидуального требования к общему предложению (1%-20%)
• Количество продуктов |P|: 5, 10, 20, 50, 100
• Параметр расстояния λ: 25м-150м
• Параметр приближения ε: 0.01-0.2

Результаты экспериментов

Основные результаты

Производительность влияния

• Набор данных NYC: Метод BCA показывает на 20-25% выше, чем базовые методы; метод RA показывает лучшие результаты
• Набор данных LA: Метод BCA показывает на 8-10% выше, чем базовые методы
• Когда α≥100% и β≥10%, спрос превышает предложение; метод BCA превосходит базовые методы, но метод RA не имеет допустимого решения

Эффективность распределения слотов

• С увеличением α и β увеличивается количество временных слотов, выделяемых каждому продукту
• Метод Top-k распределяет меньше слотов, чем метод Random
• Метод BCA распределяет больше слотов, чем методы RA и базовые (поскольку должен удовлетворить требования всех продуктов)

Вычислительная сложность

• Временная сложность:
  • Алгоритм BCA: O(n²ℓ/ε + nℓ)
  • Алгоритм RA: O(|X|·ℓ·B_max/c_min·n·t)
• Метод RA требует наибольшего времени вычисления (необходимо рассмотрение большого количества перестановок)
• Время выполнения метода BCA умеренно и растёт медленно с увеличением α и β

Эффективность затрат

• Метод RA показывает оптимальные результаты по стоимости, используя минимальные затраты для удовлетворения требований всех продуктов
• С увеличением требований затраты на распределение всех методов возрастают

Теоретические гарантии

Коэффициент приближения алгоритма BCA

Теорема: Пусть r — разреженность (максимальное количество функций, к которым может способствовать один слот), ε > 0. Алгоритм BCA с высокой вероятностью возвращает множество S, удовлетворяющее:

• Для всех j ∈ ℓ: I_j(S) ≥ (1 - 1/e - ε)·k_j
• Ожидаемая стоимость: Ec(S) = O(1/ε·log r)·OPT

Сложность выборки

Теорема: Для любых ε,δ ∈ (0,1), если размер выборки ≥ ln(2/δ)·c(BS)²/(2ε²·(W_A)²), то вероятность того, что ошибка вычисления меньше ε, составляет не менее (1-δ).

Связанные работы

Выбор временных слотов влияния

• Методы субмодульного графа: Методы на основе обрезанного субмодульного графа
• Фреймворк ветвей и границ: Фреймворк точного алгоритма
• Жадные решения: Жадные алгоритмы на основе предельного выигрыша
• Методы кооперативной коэволюции: Метод кооперативной коэволюции, предложенный Wang и др.

Минимизация сожаления

• Методы локального поиска: Решение локального поиска, предложенное Zhang и др.
• Региональные ограничения: Исследование минимизации сожаления с региональными ограничениями влияния, проведённое Ali и др.

Теоретические основы

• Задача многосубмодульного покрытия: Алгоритм случайного двукритериального приближения, предложенный Chekuri и др.
• Алгоритм непрерывной жадности: Техника непрерывного расширения для монотонных субмодульных функций

Заключение и обсуждение

Основные выводы

1. Моделирование задачи: Успешное моделирование задачи многопродуктовой рекламы на билбордах как задачи многосубмодульного покрытия и её обобщения
2. Эффективность алгоритмов: Предложенные алгоритмы показывают хорошие результаты как в теории, так и на практике
3. Практическая ценность: Методы применимы к любому сценарию многопродуктовой наружной рекламы

Ограничения

1. Вычислительная сложность: Экспоненциальная временная сложность алгоритма RA ограничивает его применение в крупномасштабных задачах
2. Предположения: Предполагается, что функция влияния обладает свойством субмодульности, что может не полностью выполняться на практике
3. Зависимость от данных: Требуется точная информация о траекториях и предпочтениях пользователей к продуктам
4. Статическая модель: Не учитываются изменения требований и предложения в динамической среде

Направления будущих исследований

1. Динамическая оптимизация: Рассмотрение изменяющихся во времени требований по влиянию и поведения пользователей
2. Онлайн-алгоритмы: Разработка алгоритмов оптимизации в реальном времени для обработки потоков данных
3. Интеграция машинного обучения: Объединение глубокого обучения для прогнозирования интересов пользователей и влияния
4. Многокритериальная оптимизация: Одновременное рассмотрение нескольких целей: стоимости, охвата и справедливости

Глубокая оценка

Преимущества

1. Значимость задачи: Решение важной задачи в реальной коммерческой среде с явной практической ценностью
2. Теоретическая строгость: Полный теоретический анализ, включая коэффициенты приближения и сложность выборки
3. Инновация алгоритмов: Умелое применение техник непрерывной жадности и случайного округления к многопродуктовому сценарию
4. Полнота экспериментов: Достаточная экспериментальная проверка на реальных наборах данных

Недостатки

1. Ограничения масштабируемости: Экспоненциальная сложность алгоритма RA ограничивает его применение к крупномасштабным задачам
2. Простота базовых методов: Методы сравнения относительно просты, отсутствует сравнение с более продвинутыми подходами
3. Недостаточный анализ чувствительности: Анализ чувствительности к ключевым параметрам (например, пороговое расстояние λ) недостаточно глубок
4. Практические ограничения: Недостаточное учёт временных ограничений и конкурентных факторов в реальной рекламной деятельности

Влияние

1. Академический вклад: Первое систематическое исследование задачи максимизации влияния многопродуктовой рекламы
2. Практическая ценность: Может быть непосредственно применено к наружной рекламе, цифровым вывескам и другим сценариям
3. Теоретическое значение: Расширение области применения теории субмодульной оптимизации в практических приложениях
4. Воспроизводимость: Предоставление подробного описания алгоритмов и экспериментальной установки

Применимые сценарии

1. Сети наружной рекламы: Оптимизация многопродуктового размещения в традиционных сетях билбордов
2. Системы цифровых вывесок: Оптимизация рекламы на цифровых экранах в торговых центрах, аэропортах и других местах
3. Транспортная реклама: Распределение рекламных мест на общественном транспорте (автобусы, метро)
4. Онлайн-реклама: Возможность расширения на задачи многопродуктовых торгов и распределения в онлайн-рекламе

Библиография

Статья ссылается на 22 соответствующих источника, включая:

• Классические работы по максимизации влияния (Kempe et al., 2003)
• Теоретические основы субмодульной оптимизации (Calinescu et al., 2007; Vondrák, 2007)
• Задачи многосубмодульного покрытия (Chekuri et al., 2022)
• Исследования рекламы на билбордах (Zhang et al., 2020, 2021)
• Теория вероятностных неравенств (Hoeffding, 1963)

Данная статья вносит важный вклад как на теоретическом, так и на практическом уровне, предоставляя систематическое решение задачи максимизации влияния многопродуктовой рекламы. Несмотря на некоторые ограничения, её инновационность и практическая ценность делают её значительным прогрессом в данной области.