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

बिलबोर्ड विज्ञापन में बहु-उत्पाद प्रभाव अधिकतमकरण

मूल जानकारी

  • पेपर ID: 2510.09050
  • शीर्षक: Multi-product Influence Maximization in Billboard Advertisement
  • लेखक: दिलदार अली (IIT जम्मू), राजीबुल इस्लाम (गांधी प्रौद्योगिकी संस्थान), सुमन बनर्जी (IIT जम्मू)
  • वर्गीकरण: cs.DS (डेटा संरचनाएं और एल्गोरिदम), cs.DB (डेटाबेस)
  • प्रकाशन समय: 25 अक्टूबर 10 (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
  • दूरी पैरामीटर λ: 25m-150m
  • सन्निकटन पैरामीटर ε: 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)

यह पेपर सैद्धांतिक और व्यावहारिक दोनों स्तरों पर महत्वपूर्ण योगदान देता है, बहु-उत्पाद प्रभाव अधिकतमकरण समस्या के लिए व्यवस्थित समाधान प्रदान करता है। कुछ सीमाओं के बावजूद, इसकी नवाचारी प्रकृति और व्यावहारिक मूल्य इसे इस क्षेत्र में महत्वपूर्ण प्रगति बनाता है।