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

تعظيم التأثير متعدد المنتجات في إعلانات اللوحات الإعلانية

المعلومات الأساسية

  • معرّف الورقة البحثية: 2510.09050
  • العنوان: Multi-product Influence Maximization in Billboard Advertisement
  • المؤلفون: Dildar Ali (معهد IIT جامو)، Rajibul Islam (معهد Gandhi للتقدم التكنولوجي)، Suman Banerjee (معهد IIT جامو)
  • التصنيف: 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. تحليل تعقيد العينات: استخدام عدم المساواة Hoeffding لتحليل تعقيد عينات خوارزمية العينات
  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. التخصيص العشوائي (RA): اختيار عشوائي للفترات الزمنية المخصصة للمنتجات
  2. تخصيص أفضل k: ترتيب حسب قيم التأثير، مع إعطاء الأولوية لتخصيص الفترات الزمنية عالية التأثير

المعاملات الرئيسية

  • نسبة الطلب والعرض α: نسبة إجمالي طلب التأثير إلى إجمالي العرض (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)

تقدم هذه الورقة مساهمات مهمة على المستويات النظرية والعملية، وتوفر حلاً منهجياً لمشكلة تعظيم التأثير متعددة المنتجات. على الرغم من وجود بعض القيود، فإن قيمتها الابتكارية والعملية تجعلها تقدماً مهماً في هذا المجال.