2025-11-22T01:49:16.464310

Fully-Dynamic Submodular Cover with Bounded Recourse

Gupta, Levin
In submodular covering problems, we are given a monotone, nonnegative submodular function $f: 2^N \rightarrow\mathbb{R}_+$ and wish to find the min-cost set $S\subseteq N$ such that $f(S)=f(N)$. This captures SetCover when $f$ is a coverage function. We introduce a general framework for solving such problems in a fully-dynamic setting where the function $f$ changes over time, and only a bounded number of updates to the solution (recourse) is allowed. For concreteness, suppose a nonnegative monotone submodular function $g_t$ is added or removed from an active set $G^{(t)}$ at each time $t$. If $f^{(t)}=\sum_{g\in G^{(t)}} g$ is the sum of all active functions, we wish to maintain a competitive solution to SubmodularCover for $f^{(t)}$ as this active set changes, and with low recourse. We give an algorithm that maintains an $O(\log(f_{max}/f_{min}))$-competitive solution, where $f_{max}, f_{min}$ are the largest/smallest marginals of $f^{(t)}$. The algorithm guarantees a total recourse of $O(\log(c_{max}/ c_{min})\cdot\sum_{t\leq T}g_t(N))$, where $c_{max},c_{min}$ are the largest/smallest costs of elements in $N$. This competitive ratio is best possible even in the offline setting, and the recourse bound is optimal up to the logarithmic factor. For monotone submodular functions that also have positive mixed third derivatives, we show an optimal recourse bound of $O(\sum_{t\leq T}g_t(N))$. This structured class includes set-coverage functions, so our algorithm matches the known $O(\log n)$-competitiveness and $O(1)$ recourse guarantees for fully-dynamic SetCover. Our work simultaneously simplifies and unifies previous results, as well as generalizes to a significantly larger class of covering problems. Our key technique is a new potential function inspired by Tsallis entropy. We also extensively use the idea of Mutual Coverage, which generalizes the classic notion of mutual information.
academic

সম্পূর্ণ-গতিশীল সাবমডিউলার কভার সীমাবদ্ধ পুনর্বিন্যাসের সাথে

মৌলিক তথ্য

  • পেপার আইডি: 2009.00800
  • শিরোনাম: Fully-Dynamic Submodular Cover with Bounded Recourse
  • লেখক: Anupam Gupta, Roie Levin (কার্নেগি মেলন বিশ্ববিদ্যালয়)
  • শ্রেণীবিভাগ: cs.DS (ডেটা স্ট্রাকচার এবং অ্যালগরিদম)
  • প্রকাশনা সময়/সম্মেলন: FOCS 2020 (IEEE 61তম বার্ষিক কম্পিউটার বিজ্ঞান ভিত্তি সিম্পোজিয়াম)
  • পেপার লিংক: https://arxiv.org/abs/2009.00800

সারসংক্ষেপ

এই পেপারটি সম্পূর্ণ-গতিশীল সেটিংয়ে সাবমডিউলার কভার সমস্যা অধ্যয়ন করে, যেখানে সাবমডিউলার ফাংশন সময়ের সাথে পরিবর্তিত হয় এবং শুধুমাত্র সীমাবদ্ধ সংখ্যক সমাধান আপডেট (পুনর্বিন্যাস) অনুমোদিত। একটি একঘেয়ে অ-নেতিবাচক সাবমডিউলার ফাংশন f:2N→R+f: 2^N \rightarrow\mathbb{R}_+ দেওয়া হলে, লক্ষ্য হল ন্যূনতম খরচের সেট S⊆NS\subseteq N খুঁজে বের করা যাতে f(S)=f(N)f(S)=f(N)। লেখকরা একটি অ্যালগরিদম প্রস্তাব করেছেন যা O(log⁡(fmax/fmin))O(\log(f_{max}/f_{min}))-প্রতিযোগিতামূলক অনুপাত সমাধান বজায় রাখে, মোট পুনর্বিন্যাস খরচ O(log⁡(cmax/cmin)⋅∑t≤Tgt(N))O(\log(c_{max}/c_{min})\cdot\sum_{t\leq T}g_t(N))। 3-বর্ধনশীল সাবমডিউলার ফাংশনের জন্য, অ্যালগরিদম সর্বোত্তম পুনর্বিন্যাস সীমানা O(∑t≤Tgt(N))O(\sum_{t\leq T}g_t(N)) অর্জন করে।

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

সমস্যা সংজ্ঞা

সাবমডিউলার কভার সমস্যা একটি ক্লাসিক NP-কঠিন সমস্যা, যখন ff একটি কভারিং ফাংশন হয় তখন এটি সেট কভার সমস্যা অন্তর্ভুক্ত করে। গতিশীল সেটিংয়ে, সাবমডিউলার ফাংশন f(t)f^{(t)} সময়ের সাথে পরিবর্তিত হয়, এবং অ্যালগরিদমকে প্রায়-সর্বোত্তম সমাধান বজায় রাখতে হবে, একই সাথে সমাধানের পরিবর্তনের পরিমাণ (পুনর্বিন্যাস) সীমাবদ্ধ করতে হবে।

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

  1. ব্যবহারিক চাহিদা: অনেক প্রয়োগ ক্ষেত্রে কভারিং চাহিদা সময়ের সাথে পরিবর্তিত হয়, যেমন নেটওয়ার্ক ফাংশন প্লেসমেন্ট, সেন্সর স্থাপনা, সামাজিক নেটওয়ার্ক প্রভাব প্রচার ইত্যাদি
  2. তাত্ত্বিক চ্যালেঞ্জ: বিদ্যমান গতিশীল অ্যালগরিদম প্রধানত সেট কভারের জন্য, সাধারণ সাবমডিউলার ফাংশন পরিচালনার জন্য একীভূত কাঠামোর অভাব
  3. পুনর্বিন্যাস সীমাবদ্ধতা: ব্যবহারিক প্রয়োগে সমাধান ঘন ঘন পরিবর্তনের খরচ অত্যন্ত বেশি, অ্যালগরিদমকে প্রতিযোগিতামূলক অনুপাত বজায় রেখে পুনর্বিন্যাস কমাতে হবে

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

  • GKKP17 শুধুমাত্র হাইপারগ্রাফ শীর্ষবিন্দু কভারের জন্য প্রযোজ্য, জটিল টোকেন বরাদ্দ প্রক্রিয়ার উপর ভিত্তি করে
  • সাধারণ সাবমডিউলার কভার সমস্যা পরিচালনার জন্য একীভূত কাঠামোর অভাব
  • কাঠামোগত সাবমডিউলার ফাংশনের জন্য সর্বোত্তম পুনর্বিন্যাস সীমানা অর্জন করতে ব্যর্থ

মূল অবদান

  1. একীভূত কাঠামো: সম্পূর্ণ-গতিশীল সাবমডিউলার কভার পরিচালনার জন্য প্রথম সাধারণ অ্যালগরিদম কাঠামো প্রস্তাব
  2. সর্বোত্তম প্রতিযোগিতামূলক অনুপাত: O(log⁡(fmax/fmin))O(\log(f_{max}/f_{min})) প্রতিযোগিতামূলক অনুপাত অর্জন, বহুপদী সময়ে সর্বোত্তম
  3. প্রায়-সর্বোত্তম পুনর্বিন্যাস: মোট পুনর্বিন্যাস O(log⁡(cmax/cmin)⋅∑tgt(N))O(\log(c_{max}/c_{min})\cdot\sum_{t}g_t(N)), শুধুমাত্র নিম্ন সীমানার চেয়ে লগারিদমিক ফ্যাক্টর বেশি
  4. কাঠামোগত ফাংশনের সর্বোত্তম সীমানা: 3-বর্ধনশীল ফাংশনের জন্য সর্বোত্তম পুনর্বিন্যাস O(∑tgt(N))O(\sum_{t}g_t(N)) অর্জন
  5. প্রযুক্তিগত উদ্ভাবন: Tsallis এন্ট্রপি-ভিত্তিক নতুন সম্ভাব্যতা ফাংশন এবং পারস্পরিক কভারিং ধারণা প্রবর্তন
  6. প্রয়োগ সম্প্রসারণ: ন্যূনতম বিস্তৃত গাছ, Steiner গাছ ইত্যাদি সমস্যার পরিচিত ফলাফল একীভূত এবং সরলীকরণ

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

কাজের সংজ্ঞা

ইনপুট:

  • উপাদান সর্বজনীন সেট NN, খরচ ফাংশন c:N→R+c: N \rightarrow \mathbb{R}_+
  • সময় ক্রম {gt}\{g_t\}, প্রতিটি gtg_t একঘেয়ে অ-নেতিবাচক সাবমডিউলার ফাংশন
  • সক্রিয় ফাংশন সেট G(t)G^{(t)}, বর্তমান ফাংশন f(t)=∑g∈G(t)gf^{(t)} = \sum_{g \in G^{(t)}} g

আউটপুট: সেট St⊆NS_t \subseteq N বজায় রাখুন যাতে f(t)(St)=f(t)(N)f^{(t)}(S_t) = f^{(t)}(N)

উদ্দেশ্য: c(St)c(S_t) এবং মোট পুনর্বিন্যাস ∑t∣St△St+1∣\sum_t |S_t \triangle S_{t+1}| কমান

মূল অ্যালগরিদম কাঠামো

পারমুটেশন রক্ষণাবেক্ষণ অ্যালগরিদম

অ্যালগরিদম উপাদানের একটি পারমুটেশন π\pi বজায় রাখে, সীমান্ত কভারিং মান সংজ্ঞায়িত করে: Fπ(πi):=f(πi∣π1:i−1)c(πi)F_\pi(\pi_i) := \frac{f(\pi_i | \pi_{1:i-1})}{c(\pi_i)}

স্থানীয় অনুসন্ধান অপারেশন:

  1. বিনিময়: যখন F(πi)≥F(πi−1)F(\pi_i) \geq F(\pi_{i-1}) তখন সংলগ্ন উপাদান বিনিময় করুন
  2. γ\gamma-চলন: উপাদান uu কে অবস্থান qq থেকে অবস্থান p<qp < q এ স্থানান্তরিত করুন, শর্ত হল সকল i∈{p,...,q−1}i \in \{p,...,q-1\} এর জন্য: Fπ′(πp′)≥γ⋅Fπ(πi)F_{\pi'}(\pi'_p) \geq \gamma \cdot F_\pi(\pi_i)

অ্যালগরিদম প্রবাহ

অ্যালগরিদম 1: সম্পূর্ণগতিশীলসাবমডিউলারকভার
1. যেকোনো পারমুটেশন π শুরু করুন
2. প্রতিটি সময় ধাপ t এর জন্য:
   a. ফাংশন g_t আগমন/প্রস্থান
   b. সকল উপাদানের কভারিং মান F_π আপডেট করুন
   c. সকল সম্ভাব্য স্থানীয় অনুসন্ধান চলন সম্পাদন করুন
   d. F_π(π_i) > 0 এর উপাদান প্রিফিক্স আউটপুট করুন

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

1. Tsallis এন্ট্রপি সম্ভাব্যতা ফাংশন

প্যারামিটারাইজড সম্ভাব্যতা ফাংশন সংজ্ঞায়িত করুন: Φα(f,π):=∑i∈N(Fπ(πi))α\Phi_\alpha(f,\pi) := \sum_{i \in N} (F_\pi(\pi_i))^\alpha

যেখানে α=(ln⁡γ)−1\alpha = (\ln \gamma)^{-1}। এই সম্ভাব্যতা ফাংশনের মূল বৈশিষ্ট্য রয়েছে:

  • ফাংশন বৃদ্ধির সময় সম্ভাব্যতা ফাংশন বৃদ্ধি নিয়ন্ত্রিত থাকে
  • স্থানীয় চলন সম্ভাব্যতা ফাংশন উল্লেখযোগ্যভাবে হ্রাস করে
  • Shannon এন্ট্রপির চেয়ে আরও কঠোর সীমানা প্রদান করে

2. পারস্পরিক কভারিং ধারণা

পারস্পরিক তথ্যকে সাবমডিউলার ফাংশনে প্রসারিত করুন: If(A;B∣C):=fC(A)+fC(B)−fC(A∪B)I_f(A;B|C) := f_C(A) + f_C(B) - f_C(A \cup B)

চেইন নিয়ম সন্তুষ্ট করে: If(A;B1∪B2∣C)=If(A;B1∣C)+If(A;B2∣C∪B1)I_f(A;B_1 \cup B_2|C) = I_f(A;B_1|C) + I_f(A;B_2|C \cup B_1)

3. 3-বর্ধনশীল ফাংশনের উন্নত অ্যালগরিদম

3-বর্ধনশীল ফাংশনের জন্য (তৃতীয় ক্রমের ডেরিভেটিভ অ-নেতিবাচক), পুনর্সংজ্ঞায়িত করুন: Fπ(πi):=∑j∈[n]Iπ,ψ(πi,ψj)c(πi)⋅c(ψj)F_\pi(\pi_i) := \sum_{j \in [n]} \frac{I_{\pi,\psi}(\pi_i, \psi_j)}{c(\pi_i) \cdot c(\psi_j)}

যেখানে ψ\psi খরচ বৃদ্ধির ক্রমে পারমুটেশন, Iπ,ψI_{\pi,\psi} পারস্পরিক সখ্যতা।

তাত্ত্বিক বিশ্লেষণ

প্রতিযোগিতামূলক অনুপাত বিশ্লেষণ

উপপাদ্য 2.1 (একক খরচ): যেকোনো γ>e\gamma > e এর জন্য, অ্যালগরিদম γ(log⁡fmax(t)/fmin(t)+1)\gamma(\log f^{(t)}_{max}/f^{(t)}_{min} + 1)-প্রতিযোগিতামূলক সমাধান বজায় রাখে।

প্রমাণ কৌশল:

  • কোনো সম্ভাব্য চলন নেই যখন, পারমুটেশন FπF_\pi মান অনুযায়ী হ্রাসমান ক্রমে সাজানো
  • প্রায়-লোভী অ্যালগরিদম সম্পাদনের ট্র্যাজেক্টরির সমতুল্য
  • মান সাবমডিউলার কভার বিশ্লেষণ প্রয়োগ করুন

পুনর্বিন্যাস সীমানা বিশ্লেষণ

লেম্মা 2.2: Tsallis সম্ভাব্যতা ফাংশন Φα\Phi_\alpha সন্তুষ্ট করে:

  1. ফাংশন বৃদ্ধির সময় বৃদ্ধি ≤gt(N)⋅(fmin)α−1\leq g_t(N) \cdot (f_{min})^{\alpha-1}
  2. ফাংশন মুছে ফেলার সময় বৃদ্ধি নেই
  3. বিনিময় অপারেশনের সময় বৃদ্ধি নেই
  4. γ\gamma-চলনের সময় হ্রাস ≥Ω((fmin)α)\geq \Omega((f_{min})^\alpha)

পুনর্বিন্যাস সীমানা: মোট পুনর্বিন্যাস≤2⋅eln⁡γγ−eln⁡γ⋅∑tgt(N)fmin\text{মোট পুনর্বিন্যাস} \leq 2 \cdot \frac{e \ln \gamma}{\gamma - e \ln \gamma} \cdot \frac{\sum_t g_t(N)}{f_{min}}

3-বর্ধনশীল ফাংশনের সর্বোত্তম সীমানা

উপপাদ্য 4.1: 3-বর্ধনশীল ফাংশনের জন্য, অ্যালগরিদম অর্জন করে:

  • প্রতিযোগিতামূলক অনুপাত: O(log⁡f(N)/fmin)O(\log f(N)/f_{min})
  • পুনর্বিন্যাস: O(∑tgt(N)/fmin)O(\sum_t g_t(N)/f_{min}) (সর্বোত্তম)

মূল অন্তর্দৃষ্টি: 3-বর্ধনশীলতা বৈশিষ্ট্য dfd{x,y,z}(S)≥0\frac{df}{d\{x,y,z\}}(S) \geq 0 শর্তাধীন অধীনে পারস্পরিক কভারিং অ-বৃদ্ধির সমতুল্য: If(x,y∣S)−If(x,y∣S∪{z})≥0I_f(x,y|S) - I_f(x,y|S \cup \{z\}) \geq 0

পরীক্ষামূলক যাচাইকরণ

তাত্ত্বিক গ্যারান্টি যাচাইকরণ

পেপারটি প্রধানত তাত্ত্বিক বিশ্লেষণ প্রদান করে, নিম্নলিখিত উপায়ে যাচাই করে:

  1. নিম্ন সীমানা মিলান: প্রমাণ করুন প্রতিযোগিতামূলক অনুপাত বহুপদী সময়ে সর্বোত্তম
  2. পুনর্বিন্যাস নিম্ন সীমানা: Ω(∑tgt(N))\Omega(\sum_t g_t(N)) প্রয়োজনীয় তা দেখাতে উদাহরণ তৈরি করুন
  3. প্যারামিটার নির্ভরশীলতা: fmax/fminf_{max}/f_{min} এবং cmax/cminc_{max}/c_{min} এর উপর নির্ভরশীলতা বিশ্লেষণ করুন

প্রয়োগ উদাহরণ

ন্যূনতম বিস্তৃত গাছ:

  • প্রতিযোগিতামূলক অনুপাত: O(1)O(1)
  • পুনর্বিন্যাস: O(log⁡D)O(\log D), যেখানে DD দূরত্ব অনুপাত

Steiner গাছ:

  • প্রতিযোগিতামূলক অনুপাত: O(1)O(1)
  • পুনর্বিন্যাস: O(log⁡D)O(\log D)

সমন্বয় অ্যালগরিদম

উপপাদ্য B.1: লোভী অ্যালগরিদম এবং র্যান্ডম অ্যালগরিদম সমন্বয় করুন, rr-junta ফাংশনের জন্য অর্জন করুন:

  • প্রতিযোগিতামূলক অনুপাত: O(min⁡(log⁡(f(N)/fmin),r))O(\min(\log(f(N)/f_{min}), r))
  • পুনর্বিন্যাস: O(RG+RPD)O(R_G + R_{PD})

সম্পর্কিত কাজ

সাবমডিউলার কভার

  • Wolsey 1982: লোভী অ্যালগরিদম (1+ln⁡fmax)(1+\ln f_{max})-আনুমানিক, সর্বোত্তম
  • Fujito 2000: ফ্রিকোয়েন্সি প্যারামিটারাইজড দ্বৈত লোভী অ্যালগরিদম
  • প্রয়োগ ক্ষেত্র: প্রভাব প্রচার, সেন্সর স্থাপনা, নেটওয়ার্ক ফাংশন স্থাপনা

গতিশীল অ্যালগরিদম

  • GKKP17: গতিশীল হাইপারগ্রাফ শীর্ষবিন্দু কভার, O(log⁡n)O(\log n) প্রতিযোগিতামূলক অনুপাত, O(1)O(1) পুনর্বিন্যাস
  • পুনর্বিন্যাস সীমাবদ্ধ অ্যালগরিদম: Steiner গাছ, ক্লাস্টারিং, ম্যাচিং, সময়সূচী ইত্যাদি সমস্যা
  • উত্তল শরীর ট্র্যাকিং: সম্পর্কিত কিন্তু প্রযুক্তিগতভাবে ভিন্ন অনলাইন অপ্টিমাইজেশন সমস্যা

উচ্চ-ক্রম একঘেয়েতা

  • Foldes & Hammer 2005: mm-বর্ধনশীল ফাংশনের সংজ্ঞা
  • Bach 2013: পরিমাপ কভারিং ফাংশনের বৈশিষ্ট্যকরণ
  • IKBA20, CM18: 3-বর্ধনশীল ফাংশনের অ্যালগরিদম এবং প্রয়োগ

সিদ্ধান্ত এবং আলোচনা

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

  1. সম্পূর্ণ-গতিশীল সাবমডিউলার কভারের জন্য প্রথম একীভূত কাঠামো প্রদান করে
  2. সাধারণ ক্ষেত্রে প্রায়-সর্বোত্তম প্রতিযোগিতামূলক অনুপাত এবং পুনর্বিন্যাস সীমানা অর্জন করে
  3. কাঠামোগত ফাংশনের জন্য (3-বর্ধনশীল) সর্বোত্তম পুনর্বিন্যাস সীমানা অর্জন করে
  4. প্রযুক্তিগত অবদান: Tsallis এন্ট্রপি সম্ভাব্যতা ফাংশন এবং পারস্পরিক কভারিং ধারণা

সীমাবদ্ধতা

  1. ফাংশন শ্রেণী সীমাবদ্ধতা: সর্বোত্তম পুনর্বিন্যাস শুধুমাত্র 3-বর্ধনশীল ফাংশনের জন্য প্রযোজ্য
  2. খরচ নির্ভরশীলতা: সাধারণ ক্ষেত্রে পুনর্বিন্যাস সীমানা log⁡(cmax/cmin)\log(c_{max}/c_{min}) এর উপর নির্ভর করে
  3. বাস্তবায়ন জটিলতা: অ্যালগরিদমের চলমান সময় জটিলতা বিশ্লেষণ করা হয়নি
  4. পরীক্ষামূলক যাচাইকরণ: বড় আকারের ব্যবহারিক প্রয়োগের পরীক্ষামূলক মূল্যায়নের অভাব

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

  1. ফাংশন শ্রেণী সম্প্রসারণ: আরও বিস্তৃত কাঠামোগত ফাংশন শ্রেণী খুঁজে বের করুন যা সর্বোত্তম পুনর্বিন্যাস অর্জন করে
  2. লগারিদমিক ফ্যাক্টর অপসারণ: সাধারণ ক্ষেত্রে log⁡(cmax/cmin)\log(c_{max}/c_{min}) নির্ভরশীলতা অপসারণ করুন
  3. অনলাইন শেখা: অনলাইন শেখার কৌশল সহ অজানা ফাংশন পরিচালনা করুন
  4. বিতরণকৃত অ্যালগরিদম: গতিশীল সাবমডিউলার কভারের বিতরণকৃত সংস্করণ ডিজাইন করুন

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

সুবিধা

  1. উল্লেখযোগ্য তাত্ত্বিক অবদান: প্রথমবার সাধারণ গতিশীল সাবমডিউলার কভার সমস্যা সমাধান করে, গুরুত্বপূর্ণ তাত্ত্বিক শূন্যতা পূরণ করে
  2. শক্তিশালী প্রযুক্তিগত উদ্ভাবন: Tsallis এন্ট্রপি সম্ভাব্যতা ফাংশনের প্রয়োগ নতুন এবং কার্যকর
  3. ফলাফলের সর্বোত্তমতা: প্রতিযোগিতামূলক অনুপাত তথ্য তাত্ত্বিক নিম্ন সীমানা অর্জন করে, পুনর্বিন্যাস সীমানা প্রায় সর্বোত্তম
  4. শক্তিশালী একীকরণ: কাঠামো একাধিক পরিচিত ফলাফল একীভূত করে, প্রমাণ সরলীকরণ করে
  5. গভীর বিশ্লেষণ: বিভিন্ন ফাংশন শ্রেণীর জন্য সূক্ষ্ম বিশ্লেষণ প্রদান করে

অপূর্ণতা

  1. ব্যবহারিক যাচাইকরণ অপর্যাপ্ত: ব্যবহারিক প্রয়োগ ক্ষেত্রের পরীক্ষামূলক যাচাইকরণের অভাব
  2. অ্যালগরিদম জটিলতা: নির্দিষ্ট সময় জটিলতা বিশ্লেষণ করা হয়নি
  3. প্যারামিটার সংবেদনশীলতা: γ\gamma ইত্যাদি প্যারামিটার নির্বাচনের জন্য নির্দেশনা অভাব
  4. সম্প্রসারণ সীমাবদ্ধতা: সর্বোত্তম ফলাফল শুধুমাত্র নির্দিষ্ট ফাংশন শ্রেণীতে প্রযোজ্য

প্রভাব

  1. তাত্ত্বিক প্রভাব: গতিশীল অপ্টিমাইজেশন অ্যালগরিদমের জন্য নতুন বিশ্লেষণ সরঞ্জাম প্রদান করে
  2. পদ্ধতিগত অবদান: সম্ভাব্যতা ফাংশন পদ্ধতি অন্যান্য গতিশীল সমস্যায় প্রযোজ্য হতে পারে
  3. প্রয়োগ সম্ভাবনা: নেটওয়ার্ক, মেশিন লার্নিং ইত্যাদি একাধিক ক্ষেত্রে সরাসরি প্রয়োগ করা যায়
  4. পরবর্তী গবেষণা: সম্পর্কিত সমস্যা গবেষণার জন্য গুরুত্বপূর্ণ ভিত্তি প্রদান করে

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

  1. নেটওয়ার্ক অপ্টিমাইজেশন: গতিশীল নেটওয়ার্ক ফাংশন স্থাপনা, রুটিং অপ্টিমাইজেশন
  2. মেশিন লার্নিং: বৈশিষ্ট্য নির্বাচন, সক্রিয় শেখায় গতিশীল নমুনা নির্বাচন
  3. সেন্সর নেটওয়ার্ক: গতিশীল সেন্সর স্থাপনা এবং পুনর্বিন্যাস
  4. সামাজিক নেটওয়ার্ক: প্রভাব প্রচারে গতিশীল নোড নির্বাচন

রেফারেন্স

মূল রেফারেন্স:

  1. Wolsey, L.A. (1982). An analysis of the greedy algorithm for the submodular set covering problem
  2. GKKP17: Online and Dynamic Algorithms for Set Cover (STOC 2017)
  3. Foldes & Hammer (2005): Submodularity, supermodularity, and higher-order monotonicities
  4. Bach, F. (2013): Learning with Submodular Functions: A Convex Optimization Perspective

প্রযুক্তিগত নোট: এই প্রতিবেদন পেপারের সম্পূর্ণ বিষয়বস্তুর উপর ভিত্তি করে তৈরি, অ্যালগরিদম ডিজাইন, তাত্ত্বিক বিশ্লেষণ এবং প্রযুক্তিগত উদ্ভাবনে ফোকাস করে। পেপারটি তাত্ত্বিক কম্পিউটার বিজ্ঞান ক্ষেত্রে গুরুত্বপূর্ণ অবদান রাখে, গতিশীল অপ্টিমাইজেশন সমস্যার জন্য নতুন গবেষণা প্যারাডাইম প্রদান করে।