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
  • লেখক: দিলদার আলী (আইআইটি জম্মু), রাজিবুল ইসলাম (গান্ধী প্রযুক্তি উন্নয়ন প্রতিষ্ঠান), সুমন বন্দ্যোপাধ্যায় (আইআইটি জম্মু)
  • শ্রেণীবিভাগ: cs.DS (ডেটা স্ট্রাকচার এবং অ্যালগরিদম), cs.DB (ডাটাবেস)
  • প্রকাশনার সময়: ২০২৫ সালের ১০ অক্টোবর (arXiv প্রি-প্রিন্ট)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2510.09050

সারসংক্ষেপ

বহিরঙ্গন বিলবোর্ড বিজ্ঞাপন একটি কার্যকর বহিরঙ্গন বিজ্ঞাপন প্রযুক্তি হয়ে উঠেছে, যার লক্ষ্য সীমিত সংখ্যক সময়কাল নির্বাচন করা এবং সেখানে বিজ্ঞাপন সামগ্রী প্রচার করা, যাতে অনেক মানুষ এটি পর্যবেক্ষণ করতে পারে এবং ব্র্যান্ডের প্রতি উল্লেখযোগ্য সংখ্যক মানুষের মনোভাব কার্যকরভাবে প্রভাবিত করতে পারে। এই পেপারটি একটি পরিবর্তিত সমস্যা অধ্যয়ন করে: বাণিজ্যিক কোম্পানিগুলি একাধিক পণ্য প্রচার করতে চায়, প্রতিটি পণ্যের নির্দিষ্ট প্রভাব প্রয়োজনীয়তা রয়েছে। দুটি সমস্যার বৈকল্পিক অধ্যয়ন করা হয়েছে: প্রথম বৈকল্পিকের লক্ষ্য k টি সময়কাল নির্বাচন করা যাতে প্রতিটি পণ্যের সংশ্লিষ্ট প্রভাব প্রয়োজনীয়তা পূরণ হয়; দ্বিতীয় বৈকল্পিকে, ℓ টি পূর্ণসংখ্যা k₁, k₂, ..., k_ℓ দেওয়া হলে, লক্ষ্য হল ℓ টি সময়কাল সেট S₁, S₂, ..., S_ℓ খুঁজে পাওয়া যা পরস্পর বিচ্ছিন্ন এবং প্রতিটি পণ্যের প্রভাব প্রয়োজনীয়তা পূরণ করে।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যার পটভূমি

১. বহিরঙ্গন বিজ্ঞাপনের গুরুত্ব: বাণিজ্যিক কোম্পানিগুলি সাধারণত মোট আয়ের ৭-১০% বিজ্ঞাপনে ব্যয় করে, বহিরঙ্গন বিলবোর্ড বিনিয়োগের রিটার্ন নিশ্চয়তা এবং ব্যবহারের সহজতার কারণে একটি কার্যকর পদ্ধতি হয়ে উঠেছে ২. ঐতিহ্যবাহী সমস্যার সীমাবদ্ধতা: বিদ্যমান গবেষণা প্রধানত একক বিজ্ঞাপনদাতার প্রভাব সর্বাধিকীকরণ বা একাধিক বিজ্ঞাপনদাতার মধ্যে অনুশোচনা ন্যূনতমকরণের উপর দৃষ্টি নিবদ্ধ করে ३. বাস্তব চাহিদা: বাণিজ্যিক কোম্পানিগুলি সাধারণত একাধিক বিজাতীয় পণ্য একযোগে প্রচার করতে প্রয়োজন, প্রতিটি পণ্য বিভিন্ন গ্রাহক গোষ্ঠীকে লক্ষ্য করে

গবেষণা প্রেরণা

  • ব্যবহারিক চাহিদা: বাস্তবে বিজ্ঞাপনদাতাদের একীভূত বাজেটের মধ্যে একাধিক পণ্যের বিভিন্ন প্রভাব প্রয়োজনীয়তা পূরণ করতে হয়
  • তাত্ত্বিক শূন্যতা: বিদ্যমান সাহিত্য বহু-পণ্য বিলবোর্ড সময়কাল নির্বাচন সমস্যার জন্য গবেষণার অভাব রয়েছে
  • প্রযুক্তিগত চ্যালেঞ্জ: প্রতিটি পণ্যের প্রভাব সীমাবদ্ধতা পূরণ করার সময় মোট খরচ ন্যূনতম করা প্রয়োজন

মূল অবদান

१. সমস্যা সম্প্রসারণ: প্রভাব সময়কাল নির্বাচন সমস্যাকে বহু-পণ্য বিজ্ঞাপন পরিস্থিতিতে সম্প্রসারিত করা, দুটি সম্পর্কিত সমস্যা বৈকল্পিক অধ্যয়ন করা २. তাত্ত্বিক মডেলিং: প্রথম বৈকল্পিককে বহু-সাবমডুলার কভারেজ সমস্যা হিসাবে মডেল করা, দ্বিতীয় বৈকল্পিককে এর সাধারণীকৃত সংস্করণ হিসাবে মডেল করা ३. অ্যালগরিদম ডিজাইন:

  • প্রথম বৈকল্পিকের জন্য দ্বৈত-মানদণ্ড আনুমানিক অ্যালগরিদম গ্রহণ করা
  • দ্বিতীয় বৈকল্পিকের জন্য নমুনা-ভিত্তিক আনুমানিক অ্যালগরিদম প্রস্তাব করা ४. দক্ষতা অপ্টিমাইজেশন: স্কেলেবিলিটি সমস্যা সমাধানের জন্য দক্ষ হিউরিস্টিক সমাধান বিকাশ করা ५. পরীক্ষামূলক যাচাইকরণ: বাস্তব ট্র্যাজেক্টরি এবং বিলবোর্ড ডেটাসেটে ব্যাপক পরীক্ষা পরিচালনা করা

পদ্ধতির বিস্তারিত বর্ণনা

কাজের সংজ্ঞা

ইনপুট:

  • ট্র্যাজেক্টরি ডাটাবেস D: ব্যবহারকারীর অবস্থান-সময় তথ্য এবং পণ্য আগ্রহ সম্পর্কিত
  • বিলবোর্ড ডাটাবেস B: বিলবোর্ড অবস্থান, সময়কাল এবং খরচ তথ্য সম্পর্কিত
  • খরচ ফাংশন c: BS → R⁺
  • পণ্য সেট P = {1,2,...,ℓ}

দুটি সমস্যা বৈকল্পিক:

१. সাধারণ বহু-পণ্য সময়কাল নির্বাচন সমস্যা:

  • একক সময়কাল সেট S ⊆ BS নির্বাচন করা
  • মোট খরচ ∑_{s∈S} c(s) ন্যূনতম করা
  • সীমাবদ্ধতা সন্তুষ্ট করা: ∀j ∈ ℓ, I_j(S) ≥ k_j

२. বিচ্ছিন্ন বহু-পণ্য সময়কাল নির্বাচন সমস্যা:

  • ℓ টি পরস্পর বিচ্ছিন্ন সময়কাল সেট S₁, S₂, ..., S_ℓ নির্বাচন করা
  • সন্তুষ্ট করা: |S_j| ≤ k_j, S_i ∩ S_j = ∅ (i≠j), I_j(S_j) ≥ σ_j

মূল প্রযুক্তি

१. প্রভাব ফাংশন মডেলিং

পণ্য 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 এর উপর প্রভাব সম্ভাবনা।

२. সাবমডুলারিটি বৈশিষ্ট্য

প্রভাব ফাংশন সাবমডুলারিটি বৈশিষ্ট্য সন্তুষ্ট করে, প্রান্তিক হ্রাস প্রভাব সন্তুষ্ট করে:

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

অ্যালগরিদম আর্কিটেকচার

অ্যালগরিদম १: সাধারণ সময়কাল নির্বাচনের জন্য দ্বৈত-মানদণ্ড আনুমানিক অ্যালগরিদম

१. স্বাভাবিকীকরণ: প্রতিটি পণ্যের প্রভাব ফাংশন স্বাভাবিক করা, যাতে I_j(BS) = 1 २. ক্রমাগত লোভী: মাল্টিলিনিয়ার এক্সটেনশন ব্যবহার করে ম্যাট্রয়েড পলিহেড্রনে ভগ্নাংশ সমাধান সমাধান করা ३. র্যান্ডম রাউন্ডিং: ℓ = ⌈log_{1/(1-ε)}(r)⌉ টি র্যান্ডম সাবসেট নমুনা করা ४. মেরামত পদক্ষেপ: অসন্তুষ্ট সীমাবদ্ধতা সহ পণ্যগুলির জন্য লোভীভাবে সময়কাল যোগ করা

অ্যালগরিদম २: বিচ্ছিন্ন সময়কাল নির্বাচনের জন্য নমুনা অ্যালগরিদম

१. ক্রমপরিবর্তন নমুনা: পণ্য-সময়কাল বরাদ্দের ক্রমপরিবর্তন র্যান্ডমভাবে নমুনা করা २. লোভী বরাদ্দ: ক্রমপরিবর্তন অনুযায়ী প্রতিটি পণ্যের জন্য লোভীভাবে সময়কাল নির্বাচন করা ३. সম্ভাব্যতা পরীক্ষা: সমস্ত সীমাবদ্ধতা সন্তুষ্ট কিনা তা যাচাই করা ४. সর্বোত্তম নির্বাচন: সর্বনিম্ন খরচের সম্ভাব্য সমাধান ফেরত দেওয়া

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

१. মাল্টিলিনিয়ার এক্সটেনশন প্রয়োগ: সাবমডুলার ফাংশনের ক্রমাগত এক্সটেনশন প্রযুক্তি বহু-পণ্য পরিস্থিতিতে প্রয়োগ করা २. নমুনা জটিলতা বিশ্লেষণ: Hoeffding অসমতা ব্যবহার করে নমুনা অ্যালগরিদমের নমুনা জটিলতা বিশ্লেষণ করা ३. দ্বৈত-মানদণ্ড আনুমানিকতা: প্রভাব সীমাবদ্ধতা সন্তুষ্ট করার সময় খরচ আনুমানিক নিশ্চয়তা প্রদান করা

পরীক্ষামূলক সেটআপ

ডেটাসেট

१. নিউইয়র্ক সিটি (NYC):

  • ২২७,४२८ চেক-ইন রেকর্ড (এপ্রিল २०१२-ফেব্রুয়ারি २०१३)
  • १,०८३ অনন্য ব্যবহারকারী
  • ७१६ বিলবোর্ড, १,०३१,०४० সময়কাল

२. লস এঞ্জেলেস (LA):

  • ७४,१७० চেক-ইন রেকর্ড, १५ টি রাস্তা জুড়ে বিস্তৃত
  • २,००० অনন্য ব্যবহারকারী
  • १,४८३ বিলবোর্ড, २,१३५,५२० সময়কাল

মূল্যায়ন মেট্রিক্স

  • প্রভাব: প্রতিটি পণ্য দ্বারা অর্জিত মোট প্রভাব
  • সময়কাল সংখ্যা: প্রতিটি পণ্যের জন্য বরাদ্দ করা মোট সময়কাল
  • গণনা সময়: অ্যালগরিদম সম্পাদন সময়
  • খরচ: সময়কাল নির্বাচনের মোট খরচ

তুলনামূলক পদ্ধতি

१. র্যান্ডম বরাদ্দ (RA): পণ্যগুলিতে সময়কাল র্যান্ডমভাবে নির্বাচন করা २. শীর্ষ-k বরাদ্দ: প্রভাব মান অনুযায়ী সাজানো, উচ্চ প্রভাব সময়কাল অগ্রাধিকার দেওয়া

মূল পরামিতি

  • চাহিদা সরবরাহ অনুপাত α: বৈশ্বিক প্রভাব চাহিদা এবং মোট সরবরাহের অনুপাত (४०%-१२०%)
  • ব্যক্তিগত চাহিদা অনুপাত β: গড় ব্যক্তিগত চাহিদা এবং মোট সরবরাহের অনুপাত (१%-२०%)
  • পণ্য সংখ্যা |P|: ५, १०, २०, ५०, १००
  • দূরত্ব পরামিতি λ: २५m-१५०m
  • আনুমানিক পরামিতি ε: ०.०१-०.२

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

প্রভাব কর্মক্ষমতা

  • NYC ডেটাসেট: BCA পদ্ধতি বেসলাইন পদ্ধতির চেয়ে २०-२५% বেশি, RA পদ্ধতি সর্বোত্তম পারফরম্যান্স প্রদর্শন করে
  • LA ডেটাসেট: BCA পদ্ধতি বেসলাইন পদ্ধতির চেয়ে ८-१०% বেশি
  • যখন α≥१००% এবং β≥१०%, চাহিদা সরবরাহ অতিক্রম করে, BCA পদ্ধতি বেসলাইনের চেয়ে উন্নত কিন্তু RA পদ্ধতির কোন সম্ভাব্য সমাধান নেই

সময়কাল বরাদ্দ দক্ষতা

  • α এবং β বৃদ্ধির সাথে, প্রতিটি পণ্যের জন্য বরাদ্দ করা সময়কাল সংখ্যা বৃদ্ধি পায়
  • শীর্ষ-k পদ্ধতি র্যান্ডম পদ্ধতির চেয়ে কম সময়কাল বরাদ্দ করে
  • 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 এবং অন্যদের র্যান্ডম দ্বৈত-মানদণ্ড আনুমানিক অ্যালগরিদম
  • ক্রমাগত লোভী অ্যালগরিদম: একক সাবমডুলার ফাংশনের ক্রমাগত এক্সটেনশন প্রযুক্তি

উপসংহার এবং আলোচনা

প্রধান উপসংহার

१. সমস্যা মডেলিং: বহু-পণ্য বিলবোর্ড সমস্যাকে বহু-সাবমডুলার কভারেজ সমস্যা এবং এর সাধারণীকরণ হিসাবে সফলভাবে মডেল করা २. অ্যালগরিদম কার্যকারিতা: প্রস্তাবিত অ্যালগরিদম তাত্ত্বিক এবং ব্যবহারিক উভয় ক্ষেত্রেই ভাল পারফরম্যান্স প্রদর্শন করে ३. ব্যবহারিক মূল্য: পদ্ধতি যেকোনো বহু-পণ্য বহিরঙ্গন বিজ্ঞাপন পরিস্থিতিতে প্রয়োগযোগ্য

সীমাবদ্ধতা

१. গণনা জটিলতা: RA অ্যালগরিদমের সূচকীয় সময় জটিলতা বড় আকারের সমস্যায় এর প্রয়োগ সীমিত করে २. অনুমান শর্তাবলী: প্রভাব ফাংশনের সাবমডুলারিটি অনুমান করা হয়, বাস্তবে সম্পূর্ণভাবে পূরণ না হতে পারে ३. ডেটা নির্ভরতা: নির্ভুল ট্র্যাজেক্টরি ডেটা এবং ব্যবহারকারী পণ্য পছন্দ তথ্য প্রয়োজন ४. স্থির মডেল: গতিশীল পরিবেশে চাহিদা এবং সরবরাহের পরিবর্তন বিবেচনা করা হয়নি

ভবিষ্যত দিকনির্দেশনা

१. গতিশীল অপ্টিমাইজেশন: সময়-পরিবর্তনশীল প্রভাব চাহিদা এবং ব্যবহারকারী আচরণ বিবেচনা করা २. অনলাইন অ্যালগরিদম: রিয়েল-টাইম ডেটা স্ট্রিম প্রক্রিয়া করার জন্য অনলাইন অপ্টিমাইজেশন অ্যালগরিদম বিকাশ করা ३. মেশিন লার্নিং একীকরণ: ব্যবহারকারীর আগ্রহ এবং প্রভাব পূর্বাভাস দিতে গভীর শিক্ষা একত্রিত করা ४. বহু-উদ্দেশ্য অপ্টিমাইজেশন: খরচ, কভারেজ এবং ন্যায্যতা সহ একাধিক উদ্দেশ্য একযোগে বিবেচনা করা

গভীর মূল্যায়ন

শক্তি

१. সমস্যার গুরুত্ব: বাস্তব ব্যবসায়িক পরিবেশে গুরুত্বপূর্ণ সমস্যা সমাধান করে, স্পষ্ট প্রয়োগ মূল্য রয়েছে २. তাত্ত্বিক কঠোরতা: সম্পূর্ণ তাত্ত্বিক বিশ্লেষণ প্রদান করে, আনুমানিক অনুপাত এবং নমুনা জটিলতা অন্তর্ভুক্ত ३. অ্যালগরিদম উদ্ভাবন: ক্রমাগত লোভী এবং র্যান্ডম রাউন্ডিং প্রযুক্তি বহু-পণ্য পরিস্থিতিতে চতুরভাবে প্রয়োগ করা ४. ব্যাপক পরীক্ষা: বাস্তব ডেটাসেটে পর্যাপ্ত পরীক্ষামূলক যাচাইকরণ পরিচালনা করা

অপূর্ণতা

१. স্কেলেবিলিটি সীমাবদ্ধতা: RA অ্যালগরিদমের সূচকীয় জটিলতা বড় আকারের সমস্যায় এর প্রয়োগ সীমিত করে २. সরল বেসলাইন পদ্ধতি: তুলনা করা বেসলাইন পদ্ধতি তুলনামূলকভাবে সহজ, আরও উন্নত পদ্ধতির সাথে তুলনার অভাব ३. পরামিতি সংবেদনশীলতা: মূল পরামিতির প্রতি সংবেদনশীলতা বিশ্লেষণ (যেমন দূরত্ব থ্রেশহোল্ড λ) যথেষ্ট গভীর নয় ४. বাস্তব সীমাবদ্ধতা: বাস্তব বিজ্ঞাপন স্থাপনে সময় সীমাবদ্ধতা এবং প্রতিযোগিতামূলক কারণ যথেষ্টভাবে বিবেচনা করা হয়নি

প্রভাব

१. একাডেমিক অবদান: বহু-পণ্য প্রভাব সর্বাধিকীকরণ সমস্যার জন্য প্রথম সিস্টেমেটিক গবেষণা প্রদান করে २. ব্যবহারিক মূল্য: বহিরঙ্গন বিজ্ঞাপন, ডিজিটাল সাইনেজ ইত্যাদি একাধিক পরিস্থিতিতে সরাসরি প্রয়োগ করা যায় ३. তাত্ত্বিক তাৎপর্য: সাবমডুলার অপ্টিমাইজেশন তত্ত্বকে ব্যবহারিক প্রয়োগে সম্প্রসারিত করে ४. পুনরুৎপাদনযোগ্যতা: বিস্তারিত অ্যালগরিদম বর্ণনা এবং পরীক্ষামূলক সেটআপ প্রদান করে

প্রযোজ্য পরিস্থিতি

१. বহিরঙ্গন বিজ্ঞাপন নেটওয়ার্ক: ঐতিহ্যবাহী বিলবোর্ড নেটওয়ার্কের বহু-পণ্য স্থাপন অপ্টিমাইজেশন २. ডিজিটাল সাইনেজ সিস্টেম: শপিং মল, বিমানবন্দর ইত্যাদি স্থানে ডিজিটাল ডিসপ্লে বিজ্ঞাপন ३. পরিবহন বিজ্ঞাপন: বাস বিজ্ঞাপন, সাবওয়ে ইত্যাদি পরিবহন বিজ্ঞাপন অবস্থান বরাদ্দ ४. অনলাইন বিজ্ঞাপন: অনলাইন বিজ্ঞাপনের বহু-পণ্য নিলাম এবং বরাদ্দ সমস্যায় সম্প্রসারণ করা যায়

সংদর্ভ

পেপারটি ২२ টি সম্পর্কিত সাহিত্য উদ্ধৃত করে, প্রধানত অন্তর্ভুক্ত:

  • প্রভাব সর্বাধিকীকরণের ক্লাসিক কাজ (Kempe et al., २००३)
  • সাবমডুলার অপ্টিমাইজেশন তাত্ত্বিক ভিত্তি (Calinescu et al., २००७; Vondrák, २००७)
  • বহু-সাবমডুলার কভারেজ সমস্যা (Chekuri et al., २०२२)
  • বিলবোর্ড বিজ্ঞাপন সম্পর্কিত গবেষণা (Zhang et al., २०२०, २०२१)
  • সম্ভাব্যতা অসমতা তত্ত্ব (Hoeffding, १९६३)

এই পেপারটি তাত্ত্বিক এবং ব্যবহারিক স্তরে গুরুত্বপূর্ণ অবদান রাখে, বহু-পণ্য প্রভাব সর্বাধিকীকরণ সমস্যার জন্য সিস্টেমেটিক সমাধান প্রদান করে। কিছু সীমাবদ্ধতা থাকলেও, এর উদ্ভাবনী এবং ব্যবহারিক মূল্য এটিকে এই ক্ষেত্রের একটি গুরুত্বপূর্ণ অগ্রগতি করে তোলে।