2025-11-22T09:19:16.214677

Approximately Bisubmodular Regret Minimization in Billboard and Social Media Advertising

Ali, Benerjee, Prasad
In a typical \emph{billboard advertisement} technique, a number of digital billboards are owned by an \emph{influence provider}, and several commercial houses approach the influence provider for a specific number of views of their advertisement content on a payment basis. If the influence provider provides the demanded or more influence, then he will receive the full payment else a partial payment. In the context of an influence provider, if he provides more or less than the advertisers demanded influence, it is a loss for him. This is formalized as 'Regret', and naturally, in the context of the influence provider, the goal will be to allocate the billboard slots among the advertisers such that the total regret is minimized. In this paper, we study this problem as a discrete optimization problem and propose two solution approaches. The first one selects the billboard slots from the available ones in an incremental greedy manner, and we call this method the Budget Effective Greedy approach. In the second one, we introduce randomness in the first one, where we do it for a sample of slots instead of calculating the marginal gains of all the billboard slots. We analyze both algorithms to understand their time and space complexity. We implement them with real-life datasets and conduct a number of experiments. We observe that the randomized budget effective greedy approach takes reasonable computational time while minimizing the regret.
academic

बिलबोर्ड और सोशल मीडिया विज्ञापन में लगभग द्विउप-मॉड्यूलर खेद न्यूनीकरण

मूल जानकारी

  • पेपर ID: 2510.09084
  • शीर्षक: Approximately Bisubmodular Regret Minimization in Billboard and Social Media Advertising
  • लेखक: दिलदार अली, सुमन बनर्जी, यमुना प्रसाद (भारतीय प्रौद्योगिकी संस्थान जम्मू)
  • वर्गीकरण: cs.GT (गेम थ्योरी), cs.DB (डेटाबेस), cs.DS (डेटा संरचनाएं और एल्गोरिदम)
  • प्रकाशन समय: अक्टूबर 2025 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2510.09084

सारांश

यह पेपर बहु-मोडल विज्ञापन वातावरण में खेद न्यूनीकरण की समस्या का अध्ययन करता है, जहां प्रभाव प्रदाता को एक साथ बिलबोर्ड समय स्लॉट और सोशल मीडिया सीड नोड्स को कई विज्ञापनदाताओं को आवंटित करने की आवश्यकता होती है। लेखकों ने दो विभिन्न विज्ञापन माध्यमों के व्यक्तिगत और संयुक्त प्रभावों को पकड़ने के लिए एक नई इंटरैक्शन प्रभाव मॉडल प्रस्तावित की है, और दो समाधान डिजाइन किए हैं: प्रोजेक्टेड सबग्रेडिएंट विधि (PGM) और लगभग द्विउप-मॉड्यूलर स्थानीय खोज (ABLS)। प्रयोग विभिन्न मांग सेटिंग्स के तहत प्रस्तावित विधियों की प्रभावशीलता को दर्शाते हैं।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

  1. मुख्य समस्या: प्रभाव प्रदाता बिलबोर्ड और सोशल मीडिया विज्ञापन के बीच संयुक्त रूप से संसाधनों को कैसे आवंटित करें ताकि कुल खेद को कम किया जा सके
  2. व्यावहारिक परिदृश्य: व्यावसायिक कंपनियां प्रभाव प्रदाताओं को दैनिक प्रस्ताव प्रस्तुत करती हैं जिनमें प्रभाव आवश्यकताएं होती हैं, ऑनलाइन और ऑफलाइन मोड को कवर करते हुए, और मांग पूर्ति के आधार पर सशर्त भुगतान करते हैं

अनुसंधान का महत्व

  • व्यावसायिक कंपनियां आमतौर पर वार्षिक राजस्व का 7-10% विज्ञापन पर खर्च करती हैं
  • मौजूदा अनुसंधान मुख्य रूप से विज्ञापनदाता के दृष्टिकोण से है, प्रभाव प्रदाता के दृष्टिकोण से संयुक्त अनुकूलन की कमी है
  • पारंपरिक विधियां बिलबोर्ड और सोशल मीडिया के बीच इंटरैक्शन प्रभावों को नजरअंदाज करती हैं

मौजूदा विधियों की सीमाएं

  • मौजूदा साहित्य बिलबोर्ड और सोशल मीडिया विज्ञापन के खेद मॉडल को अलग से संभालता है
  • दोनों विज्ञापन मोड के इंटरैक्शन प्रभावों पर विचार करने वाली एकीकृत रूपरेखा की कमी है
  • मौजूदा खेद मॉडल गैर-एकरस और गैर-उप-मॉड्यूलर हैं, जिससे प्रदर्शन गारंटी अप्राप्य हैं

मुख्य योगदान

  1. पहली संयुक्त मॉडलिंग: बिलबोर्ड और सोशल नेटवर्क विज्ञापन दोनों पर विचार करने वाली खेद न्यूनीकरण समस्या प्रस्तावित की गई है
  2. सैद्धांतिक विश्लेषण: साबित किया गया कि समस्या NP-कठिन है और किसी भी स्थिर कारक के भीतर अनुमानित नहीं है
  3. एल्गोरिदम डिजाइन: दो समाधान प्रस्तावित किए गए हैं: प्रोजेक्टेड सबग्रेडिएंट विधि (PGM) और लगभग द्विउप-मॉड्यूलर स्थानीय खोज (ABLS)
  4. इंटरैक्शन प्रभाव मॉडल: बिलबोर्ड और सोशल मीडिया के बीच इंटरैक्शन प्रभावों का गणितीय मॉडलिंग
  5. प्रायोगिक सत्यापन: वास्तविक डेटासेट पर विधियों की प्रभावशीलता का सत्यापन

विधि विवरण

कार्य परिभाषा

इनपुट:

  • बिलबोर्ड समय स्लॉट सेट BS = {bs₁, bs₂, ..., bsₘ}
  • सोशल नेटवर्क सीड नोड्स सेट P = {p₁, p₂, ..., pᵣ}
  • विज्ञापनदाता सेट A = {a₁, a₂, ..., aₙ}, प्रत्येक विज्ञापनदाता के पास प्रभाव आवश्यकता σᵢ और बजट Kᵢ है

आउटपुट:

  • आवंटन योजना L = {(S₁,P₁), (S₂,P₂), ..., (Sₙ,Pₙ)}, जो कुल खेद को कम करती है

बाधा शर्तें:

  • पारस्परिक एक्सक्लूसिविटी बाधा: विभिन्न विज्ञापनदाताओं के आवंटन ओवरलैप नहीं कर सकते
  • बजट बाधा: आवंटन लागत विज्ञापनदाता के बजट से अधिक नहीं हो सकती

मुख्य मॉडल

1. प्रभाव मॉडल

Φ(S,P) = I(S) + IG(P) + Ψ(S,P)

जहां:

  • I(S): बिलबोर्ड समय स्लॉट सेट S का प्रभाव
  • IG(P): सीड नोड्स सेट P का प्रभाव
  • Ψ(S,P): इंटरैक्शन प्रभाव

2. इंटरैक्शन प्रभाव मॉडल

Ψ(S,P) = ρ · Σᵤ∈U (1 - ∏ᵦ∈S(1 - Pr(u,b))) · Σᵥ∈P Pr'(u,v)

जहां ρ ∈ 0,1 इंटरैक्शन की तीव्रता को नियंत्रित करता है

3. खेद मॉडल

R(Naᵢ) = Kaᵢ · (1 - γ · min(Φ(Saᵢ,Paᵢ),σaᵢ)/σaᵢ) + δ · log(1 + |Saᵢ| + |Paᵢ|)

एल्गोरिदम डिजाइन

1. प्रोजेक्टेड सबग्रेडिएंट विधि (PGM)

  • Lovász एक्सटेंशन के आधार पर निरंतर अनुकूलन विधि
  • समय स्लॉट और सीड के नरम चयन को दर्शाने के लिए भिन्नात्मक वेक्टर का उपयोग
  • सबग्रेडिएंट डिसेंट और प्रोजेक्शन चरणों के माध्यम से पुनरावृत्तीय अपडेट
  • समय जटिलता: O(T·m³·n·r·t + Tm²·n·r²·t + m⁴·n·r·t + m³·n·r²·t + m²·n·r³·t)

2. लगभग द्विउप-मॉड्यूलर स्थानीय खोज (ABLS)

  • लालची स्थानीय खोज विधि
  • बजट आवश्यकता अनुपात के अवरोही क्रम में विज्ञापनदाताओं को क्रमबद्ध करें
  • प्रति इकाई प्रभाव खेद में सबसे बड़ी कमी वाले तत्व का चयन करें
  • समय जटिलता: O(m·r²·t + m²·r·t)

तकनीकी नवाचार बिंदु

  1. ε-अनुमानित द्विउप-मॉड्यूलरता: पारंपरिक द्विउप-मॉड्यूलर फ़ंक्शन को विस्तारित करता है, बंधी हुई विचलन की अनुमति देता है
  2. एकीकृत रूपरेखा: पहली बार बिलबोर्ड और सोशल मीडिया विज्ञापन को एकीकृत मॉडलिंग
  3. इंटरैक्शन प्रभाव परिमाणीकरण: इंटरैक्शन प्रभाव गणना के लिए गणितीय विधि प्रदान करता है
  4. सैद्धांतिक गारंटी: अनुमानित द्विउप-मॉड्यूलर फ़ंक्शन के लिए प्रदर्शन सीमाएं प्रदान करता है

प्रायोगिक सेटअप

डेटासेट

  1. ट्रैजेक्टरी डेटा: Foursquare चेक-इन डेटा (2012.4-2014.1)
    • 124,539 चेक-इन, 51,318 अद्वितीय उपयोगकर्ता
    • अमेरिका के प्रमुख शहरों को कवर करता है
  2. सोशल नेटवर्क डेटा: उपयोगकर्ता सोशल नेटवर्क स्नैपशॉट
    • पुराना नेटवर्क: 95,994 मित्रता संबंध
    • नया नेटवर्क: 129,864 मित्रता संबंध
  3. बिलबोर्ड डेटा: LAMAR डेटासेट
    • न्यूयॉर्क: 716 बिलबोर्ड, 1,031,040 समय स्लॉट
    • लॉस एंजिल्स: 1,483 बिलबोर्ड, 2,135,520 समय स्लॉट

मूल्यांकन मेट्रिक्स

  • कुल खेद: सभी विज्ञापनदाताओं के खेद का योग
  • संतुष्ट विज्ञापनदाताओं की संख्या: जिन विज्ञापनदाताओं की मांग पूरी हुई
  • कम्प्यूटेशनल समय: एल्गोरिदम चलने का समय

तुलना विधियां

  • यादृच्छिक आवंटन (RA): बिलबोर्ड समय स्लॉट और सीड नोड्स को यादृच्छिक रूप से चुनें
  • शीर्ष-k आवंटन: सबसे प्रभावशाली k बिलबोर्ड समय स्लॉट और सीड नोड्स चुनें

मुख्य पैरामीटर

पैरामीटरअर्थमान श्रेणी
αमांग-आपूर्ति अनुपात40%-120%
λऔसत व्यक्तिगत मांग अनुपात1%-20%
γअपूर्ण दंड अनुपात0-1
δकार्डिनैलिटी दंड अनुपात0-1
εखेद सहनशीलता पैरामीटर0-0.1
ρइंटरैक्शन पैरामीटर0-1

प्रायोगिक परिणाम

मुख्य परिणाम

1. विभिन्न मांग परिदृश्यों के तहत प्रदर्शन

केस 1 (कम α, कम λ): α ≤ 80%, λ ≤ 2%

  • PGM और ABLS आधारभूत विधियों से काफी बेहतर हैं
  • अधिक संतुष्ट विज्ञापनदाता
  • खेद में 30-40% की कमी

केस 2 (कम α, उच्च λ): α ≤ 80%, λ ≥ 5%

  • उच्च व्यक्तिगत मांग के समय, अत्यधिक आपूर्ति में कमी
  • प्रस्तावित विधियां अभी भी लाभ बनाए रखती हैं
  • खेद में 25-35% की कमी

केस 3 (उच्च α, कम λ): α ≥ 100%, λ ≤ 2%

  • अपर्याप्त आपूर्ति से समग्र खेद में वृद्धि
  • PGM और ABLS अभी भी आधारभूत से बेहतर हैं
  • खेद में 15-25% की कमी

केस 4 (उच्च α, उच्च λ): α ≥ 100%, λ ≥ 5%

  • सभी विधियां उच्च खेद का सामना करती हैं
  • कुछ उच्च-मांग विज्ञापनदाता कई कम-मांग विज्ञापनदाताओं जितना अनुकूल नहीं हैं

2. कम्प्यूटेशनल दक्षता विश्लेषण

  • ABLS अधिकांश मामलों में कम्प्यूटेशनल समय में तेजी से है
  • PGM विज्ञापनदाताओं की संख्या अधिक होने पर कम्प्यूटेशनल ओवरहेड में काफी वृद्धि करता है
  • मांग-आपूर्ति अनुपात α बढ़ने के साथ, सभी विधियों का कम्प्यूटेशनल समय बढ़ता है

3. पैरामीटर संवेदनशीलता विश्लेषण

  • ε में वृद्धि: चलने का समय कम होता है लेकिन खेद बढ़ता है
  • δ में वृद्धि: बड़े आवंटन को दंडित करता है, जिससे कॉम्पैक्ट लेकिन कम प्रभावी समाधान होता है
  • γ में वृद्धि: मांग पूर्ति पर जोर देता है, उच्च संसाधन उपयोग के बदले में कम खेद
  • ρ में वृद्धि: बिलबोर्ड और सीड नोड्स के बीच इंटरैक्शन की तीव्रता बढ़ता है

विलोपन प्रयोग

  1. इंटरैक्शन प्रभाव का प्रभाव:
    • इंटरैक्शन प्रभाव पर विचार करते समय कुल खेद 341.37 से घटकर 295.14 हो गया
    • इंटरैक्शन प्रभाव मॉडलिंग के महत्व को साबित करता है
  2. संभाव्यता सेटिंग का प्रभाव:
    • त्रिमुखी संभाव्यता सेटिंग (trivalency) सर्वश्रेष्ठ प्रदर्शन करती है
    • व्यक्तियों के बीच प्रभाव में वास्तविक परिवर्तनशीलता को बेहतर तरीके से मॉडल करता है

स्केलेबिलिटी परीक्षण

  • बड़े पैमाने पर परिदृश्य: λ = 1%, |A| = 100
  • छोटे पैमाने पर परिदृश्य: λ = 20%, |A| = 5
  • दोनों परिदृश्यों में PGM और ABLS आधारभूत विधियों से बेहतर हैं

संबंधित कार्य

प्रभाव अधिकतमकरण अनुसंधान

  • बिलबोर्ड विज्ञापन में प्रभाव अधिकतमकरण 6, 33, 36
  • सोशल नेटवर्क विज्ञापन में प्रभाव अधिकतमकरण 17, 19, 24
  • संयुक्त लेबल और समय स्लॉट चयन समस्या 7

खेद न्यूनीकरण अनुसंधान

  • सोशल नेटवर्क में खेद न्यूनीकरण 13, 30
  • बिलबोर्ड विज्ञापन में खेद न्यूनीकरण 37
  • क्षेत्रीय प्रभाव बाधाओं के तहत खेद न्यूनीकरण 2, 4

इस पेपर का योगदान

यह पेपर बिलबोर्ड और सोशल नेटवर्क विज्ञापन दोनों पर विचार करने वाला पहला खेद न्यूनीकरण अनुसंधान है, जो इस क्षेत्र में एक अंतराल को भरता है।

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. समस्या जटिलता: साबित किया गया कि बहु-मोडल विज्ञापन खेद न्यूनीकरण समस्या NP-कठिन है और अनुमानित नहीं है
  2. एल्गोरिदम प्रभावशीलता: PGM और ABLS विभिन्न सेटिंग्स के तहत खेद को प्रभावी ढंग से कम कर सकते हैं
  3. इंटरैक्शन प्रभाव का महत्व: बिलबोर्ड और सोशल मीडिया के बीच इंटरैक्शन प्रभाव पर विचार करने से परिणामों में काफी सुधार हो सकता है
  4. व्यावहारिक मार्गदर्शन: कुछ उच्च-मांग विज्ञापनदाताओं की तुलना में कई कम-मांग विज्ञापनदाता अधिक लाभदायक हैं

सीमाएं

  1. कम्प्यूटेशनल जटिलता: PGM बड़े पैमाने पर परिदृश्यों में कम्प्यूटेशनल ओवरहेड में अधिक है
  2. पैरामीटर संवेदनशीलता: कई पैरामीटर को सावधानीपूर्वक ट्यून करने की आवश्यकता है
  3. इंटरैक्शन मॉडल सरलीकरण: इंटरैक्शन प्रभाव मॉडल वास्तविक जटिलता को पूरी तरह से पकड़ नहीं सकता है
  4. स्थिर सेटिंग: गतिशील रूप से आने वाले विज्ञापनदाताओं के परिदृश्य पर विचार नहीं किया गया है

भविष्य की दिशाएं

  1. ऑनलाइन एल्गोरिदम: गतिशील विज्ञापनदाता आगमन को संभालने वाले ऑनलाइन एल्गोरिदम विकसित करें
  2. समानांतर अनुकूलन: स्केलेबिलिटी में सुधार के लिए समानांतर और वितरित अनुकूलन रूपरेखा डिजाइन करें
  3. अधिक जटिल इंटरैक्शन मॉडल: इंटरैक्शन प्रभाव के अधिक सटीक मॉडलिंग विधियों का अन्वेषण करें
  4. अन्य अनुप्रयोग क्षेत्र: क्लाउड कम्प्यूटिंग संसाधन आवंटन जैसे अन्य क्षेत्रों में रूपरेखा का विस्तार करें

गहन मूल्यांकन

शक्तियां

  1. समस्या की नवीनता: बहु-मोडल विज्ञापन के संयुक्त खेद न्यूनीकरण का पहली बार अध्ययन, महत्वपूर्ण व्यावहारिक महत्व के साथ
  2. सैद्धांतिक कठोरता: पूर्ण सैद्धांतिक विश्लेषण, जटिलता प्रमाण और अनुमान गारंटी सहित
  3. विधि नवाचार:
    • ε-अनुमानित द्विउप-मॉड्यूलरता की अवधारणा प्रस्तावित की
    • इंटरैक्शन प्रभाव के लिए गणितीय मॉडल डिजाइन किया
    • दो पूरक एल्गोरिदम विकसित किए
  4. प्रायोगिक पूर्णता:
    • वास्तविक बड़े पैमाने पर डेटासेट का उपयोग
    • कई पैरामीटर सेटिंग्स और परिदृश्यों पर विचार
    • विस्तृत विलोपन प्रयोग और संवेदनशीलता विश्लेषण प्रदान करता है

कमजोरियां

  1. इंटरैक्शन मॉडल की सीमा: इंटरैक्शन प्रभाव की रैखिक संयोजन धारणा बहुत सरल हो सकती है
  2. कम्प्यूटेशनल दक्षता: PGM की समय जटिलता अधिक है, व्यावहारिक अनुप्रयोग में चुनौतियों का सामना कर सकता है
  3. पैरामीटर निर्भरता: एल्गोरिदम प्रदर्शन कई पैरामीटर के प्रति संवेदनशील है, वास्तविक तैनाती में सावधानीपूर्वक ट्यूनिंग की आवश्यकता है
  4. मूल्यांकन सीमा: अधिक उन्नत आधारभूत विधियों के साथ तुलना की कमी

प्रभाव

  1. शैक्षणिक योगदान:
    • बहु-मोडल विज्ञापन अनुकूलन के नए अनुसंधान दिशा की स्थापना
    • अनुमानित द्विउप-मॉड्यूलर फ़ंक्शन के लिए उप-मॉड्यूलर अनुकूलन सिद्धांत का विस्तार
    • संबंधित अनुकूलन समस्याओं के लिए सैद्धांतिक आधार प्रदान करता है
  2. व्यावहारिक मूल्य:
    • डिजिटल विज्ञापन उद्योग में सीधे लागू
    • रूपरेखा क्लाउड कम्प्यूटिंग, लॉजिस्टिक्स आदि में संसाधन आवंटन समस्याओं तक विस्तारित हो सकती है
    • प्रभाव प्रदाताओं के लिए निर्णय समर्थन उपकरण प्रदान करता है
  3. पुनरुत्पादनीयता: पेपर विस्तृत एल्गोरिदम विवरण और प्रायोगिक सेटअप प्रदान करता है, पुनरुत्पादन को सुविधाजनक बनाता है

लागू परिदृश्य

  1. डिजिटल विज्ञापन प्लेटफॉर्म: ऑनलाइन और ऑफलाइन विज्ञापन संसाधनों को एक साथ प्रबंधित करने की आवश्यकता वाले प्लेटफॉर्म के लिए लागू
  2. संसाधन आवंटन प्रणाली: क्लाउड कम्प्यूटिंग, लॉजिस्टिक्स आदि क्षेत्रों में संसाधन आवंटन समस्याओं तक विस्तारित हो सकता है
  3. प्रभाव विपणन: सोशल मीडिया विपणन और पारंपरिक विज्ञापन के संयुक्त अनुकूलन के लिए लागू

संदर्भ

पेपर 37 संबंधित संदर्भों का हवाला देता है, जो प्रभाव अधिकतमकरण, उप-मॉड्यूलर अनुकूलन, विज्ञापन आवंटन आदि कई अनुसंधान क्षेत्रों के महत्वपूर्ण कार्यों को कवर करता है, जो इस अनुसंधान के लिए एक मजबूत सैद्धांतिक आधार प्रदान करता है।

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