2025-11-25T08:04:18.158681

Adaptivity Gaps for Stochastic Probing with Subadditive Functions

Li, Liu, Zhang
In this paper, we study the stochastic probing problem under a general monotone norm objective. Given a ground set $U = [n]$, each element $i \in U$ has an independent nonnegative random variable $X_i$ with known distribution. Probing an element reveals its value, and the sequence of probed elements must satisfy a prefix-closed feasibility constraint $\mathcal{F}$. A monotone norm $f: \mathbb{R}_{\geq 0}^n \to \mathbb{R}_{\geq 0}$ determines the reward $f(X_P)$, where $P$ is the set of probed elements and $X_P$ is the vector with $X_i$ for $i \in P$ and 0 otherwise. The goal is to design a probing strategy maximizing the expected reward $\mathbb{E}[f(X_P)]$. We focus on the adaptivity gap: the ratio between the expected rewards of optimal adaptive and optimal non-adaptive strategies. We resolve an open question posed in [GNS17, KMS24], showing that for general monotone norms, the adaptivity gap is $O(\log^2 n)$. A refined analysis yields an improved bound of $O(\log r \log n / \log\log n)$, where $r$ is the maximum size of a feasible probing sequence. As a by-product, we derive an asymptotically tight adaptivity gap $Θ( \log n/\log\log n)$ for Bernoulli probing with binary-XOS objectives, matching the known lower bound. Additionally, we show an $O(\log^3 n)$ upper bound for Bernoulli probing with general subadditive objectives. For monotone symmetric norms, we prove the adaptivity gap is $O(1)$, improving the previous $O(\log n)$ bound from [PRS23].
academic

সাবঅ্যাডিটিভ ফাংশনের সাথে স্টোকাস্টিক প্রোবিং এর অ্যাডাপটিভিটি গ্যাপ

মৌলিক তথ্য

  • পেপার আইডি: 2504.15547
  • শিরোনাম: Adaptivity Gaps for Stochastic Probing with Subadditive Functions
  • লেখক: জিয়ান লি, ইনচেন লিউ, ইরান ঝাং (তিংহুয়া বিশ্ববিদ্যালয় ক্রস ডিসিপ্লিনারি ইনফরমেশন রিসার্চ ইনস্টিটিউট)
  • শ্রেণীবিভাগ: cs.DS (ডেটা স্ট্রাকচার এবং অ্যালগরিদম)
  • প্রকাশনার সময়: ২০২৪ সালের এপ্রিল (arXiv সংস্করণ, সর্বশেষ আপডেট ২০২৫ সালের অক্টোবর)
  • পেপার লিংক: https://arxiv.org/abs/2504.15547v2

সারসংক্ষেপ

এই পেপারটি সাধারণ মনোটোন নর্ম উদ্দেশ্যের অধীনে স্টোকাস্টিক প্রোবিং সমস্যা অধ্যয়ন করে। ভিত্তি সেট U=[n]U = [n] দেওয়া হলে, প্রতিটি উপাদান i∈Ui \in U একটি পরিচিত বিতরণের স্বাধীন অ-নেতিবাচক র্যান্ডম ভেরিয়েবল XiX_i এর সাথে যুক্ত। উপাদান প্রোব করা এর মান প্রকাশ করে, প্রোবিং ক্রম অবশ্যই প্রিফিক্স-বন্ধ সম্ভাব্যতা সীমাবদ্ধতা F\mathcal{F} সন্তুষ্ট করতে হবে। মনোটোন নর্ম f:R≥0n→R≥0f: \mathbb{R}_{\geq 0}^n \to \mathbb{R}_{\geq 0} পুরস্কার f(XP)f(X_P) নির্ধারণ করে, যেখানে PP হল প্রোব করা উপাদানের সেট। লক্ষ্য হল প্রত্যাশিত পুরস্কার সর্বাধিক করার জন্য প্রোবিং কৌশল ডিজাইন করা। এই পেপারটি অ্যাডাপটিভিটি গ্যাপের উপর ফোকাস করে: সর্বোত্তম অ্যাডাপটিভ কৌশল এবং সর্বোত্তম অ-অ্যাডাপটিভ কৌশলের প্রত্যাশিত পুরস্কারের অনুপাত।

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

সমস্যার গুরুত্ব

স্টোকাস্টিক প্রোবিং সমস্যা অনিশ্চয়তা অপ্টিমাইজেশনে একটি মৌলিক কাঠামো, যা ব্যাপকভাবে প্রয়োগ করা হয়:

  • বেয়েসিয়ান মেকানিজম ডিজাইন
  • অনলাইন শিক্ষা
  • প্রভাব সর্বাধিকীকরণ
  • রোবোটিক পাথ পরিকল্পনা
  • ডাটাবেস ব্যবস্থাপনা

অ্যাডাপটিভিটি গ্যাপের তাৎপর্য

  1. তাত্ত্বিক তাৎপর্য: অ্যাডাপটিভিটির মূল্য পরিমাপ করা, বোঝা যে কখন সহজ অ-অ্যাডাপটিভ কৌশল যথেষ্ট ভাল
  2. ব্যবহারিক মূল্য: অ-অ্যাডাপটিভ কৌশলগুলি প্রতিনিধিত্ব, বিশ্লেষণ এবং বাস্তবায়ন করা সহজ, বড় সিদ্ধান্ত গাছ বজায় রাখার গণনামূলক ওভারহেড এড়ায়
  3. অ্যালগরিদম ডিজাইন নির্দেশনা: ছোট অ্যাডাপটিভিটি গ্যাপ অ-অ্যাডাপটিভ কৌশলগুলিতে ফোকাস করার যুক্তিযুক্ততা প্রমাণ করে

বিদ্যমান কাজের সীমাবদ্ধতা

  • গুপ্তা এবং অন্যরা GNS17 সাবঅ্যাডিটিভ ফাংশনের অ্যাডাপটিভিটি গ্যাপ সম্পর্কে অনুমান করেছেন, এটি মাল্টি-লগারিদমিক বলে বিশ্বাস করেন
  • প্যাটন এবং অন্যরা PRS23 সমরূপ নর্মের জন্য O(log⁡n)O(\log n) উপরের সীমা প্রমাণ করেছেন, কিন্তু অনুমান করেন যে প্রকৃত গ্যাপ ধ্রুবক হতে পারে
  • কেসেলহেইম এবং অন্যরা KMS24 অনুমানটি সাধারণ মনোটোন নর্মে প্রসারিত করেছেন

মূল অবদান

  1. মূল খোলা সমস্যা সমাধান: সাধারণ মনোটোন নর্মের অ্যাডাপটিভিটি গ্যাপ O(log⁡2n)O(\log^2 n) প্রমাণ করা, পরিমার্জিত বিশ্লেষণ O(log⁡rlog⁡n/log⁡log⁡n)O(\log r \log n / \log\log n) প্রদান করা
  2. কঠোর সীমা অর্জন: বাইনারি XOS উদ্দেশ্যের বার্নুলি প্রোবিং এর জন্য, অ্যাডাপটিভিটি গ্যাপ Θ(log⁡n/log⁡log⁡n)\Theta(\log n/\log\log n) প্রমাণ করা, পরিচিত নিম্ন সীমার সাথে মিলিত
  3. সাবঅ্যাডিটিভ ফাংশন সীমা উন্নত করা: বার্নুলি প্রোবিং এর অধীনে সাধারণ সাবঅ্যাডিটিভ উদ্দেশ্যের অ্যাডাপটিভিটি গ্যাপ O(log⁡3n)O(\log^3 n) প্রমাণ করা
  4. ধ্রুবক সীমা ফলাফল: মনোটোন সমরূপ নর্মের জন্য, অ্যাডাপটিভিটি গ্যাপ O(log⁡n)O(\log n) থেকে O(1)O(1) এ উন্নত করা

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

কাজের সংজ্ঞা

স্টোকাস্টিক প্রোবিং সমস্যা:

  • ইনপুট: ভিত্তি সেট U=[n]U = [n], প্রতিটি উপাদান ii র্যান্ডম ভেরিয়েবল XiX_i এর সাথে যুক্ত, উদ্দেশ্য ফাংশন ff, সম্ভাব্যতা সীমাবদ্ধতা F\mathcal{F}
  • প্রক্রিয়া: অভিযোজনশীলভাবে উপাদান প্রোব করা, বাস্তবায়িত মান পর্যবেক্ষণ করা, পাতা নোডে পৌঁছানো পর্যন্ত
  • আউটপুট: প্রোব করা উপাদানের সেট PP, পুরস্কার f(XP)f(X_P) অর্জন করা
  • লক্ষ্য: প্রত্যাশিত পুরস্কার E[f(XP)]\mathbb{E}[f(X_P)] সর্বাধিক করা

অ্যাডাপটিভিটি গ্যাপ: সর্বোত্তম অ্যাডাপটিভ কৌশলের প্রত্যাশিত পুরস্কারসর্বোত্তম অ-অ্যাডাপটিভ কৌশলের প্রত্যাশিত পুরস্কার\frac{\text{সর্বোত্তম অ্যাডাপটিভ কৌশলের প্রত্যাশিত পুরস্কার}}{\text{সর্বোত্তম অ-অ্যাডাপটিভ কৌশলের প্রত্যাশিত পুরস্কার}}

মূল প্রযুক্তিগত কাঠামো

১. তিন-ধাপ হ্রাস কৌশল

পেপারটি একটি পদ্ধতিগত হ্রাস পদ্ধতি গ্রহণ করে:

প্রথম ধাপ: সাধারণ র্যান্ডম ভেরিয়েবল → বার্নুলি সেটিং

  • λ\lambda-বড় বিয়োজন কৌশল ব্যবহার করা
  • ক্রমাগত বিতরণকে নেতিবাচক 2 শক্তিতে বিচ্ছিন্ন করা
  • সিদ্ধান্ত গাছকে বাইনারি গাছে রূপান্তর করা

দ্বিতীয় ধাপ: সাধারণ XOS → বিশেষ XOS নর্ম

  • ওজনকে নেতিবাচক 2 শক্তিতে বৃত্তাকার করা
  • বিশেষ ফর্ম তৈরি করা: fxos(S)=max⁡ℓ{∣elt(Aℓ′)∩S∣}f_{xos}(S) = \max_\ell \{|\text{elt}(A'_\ell) \cap S|\}
  • শুধুমাত্র O(log⁡r)O(\log r) ফ্যাক্টর হারানো

তৃতীয় ধাপ: লোভী অ্যালগরিদম বিশ্লেষণ

  • গভীরতা তথ্য নিয়ন্ত্রণ করার জন্য জটিল লেবেল সিস্টেম ডিজাইন করা
  • লেজ সম্ভাব্যতা সীমা প্রমাণ করা
  • প্রযুক্তিগত অসমতা প্রয়োগ করা

২. মূল অ্যালগরিদম ডিজাইন

লোভী লেবেল অ্যালগরিদম:

ইনপুট: (ℓ, R)
আউটপুট: লেবেল B = (m; s; d₁,...,dₘ; e₁,...,eₘ; y₁,...,y⌊s/K⌋)

1. শুরু করা: s ← |A'_ℓ|, d₁ ← depth(ℓ)
2. গভীরতা নিয়ন্ত্রণ পরামিতি yᵢ সেট করা
3. পথ Pₓ এর সাথে প্রতিটি নোড u এর উপর দিয়ে যাওয়া:
   - পরীক্ষা করা u ∈ R এবং উপযুক্ত পাতা ℓ' বিদ্যমান
   - শর্ত পূরণ হলে, লেবেল B আপডেট করা
4. চূড়ান্ত লেবেল B ফেরত দেওয়া

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

গভীরতা নিয়ন্ত্রণ প্রক্রিয়া:

  • পরামিতি K=O(log⁡n)K = O(\log n) ব্যবহার করে Aℓ′A'_\ell এ উপাদানের গভীরতা নিয়ন্ত্রণ করা
  • প্রতিটি jj এর জন্য, yjy_j Aℓ′A'_\ell এ jKjK তম উপাদানের গভীরতা প্রতিনিধিত্ব করে
  • বিভিন্ন পাতার মধ্যে Aℓ′A'_\ell কাঠামোর সাদৃশ্য নিশ্চিত করা

অসম্ভব নোড সনাক্তকরণ:

  • সংজ্ঞা Imp(ℓ,B0)\text{Imp}(\ell, B_0): প্রদত্ত লেবেলের অধীনে সক্রিয় করা যায় না এমন নোড সেট
  • প্রমাণ করা প্রতিটি ℓ∈S(B0)\ell \in S(B_0) এ কমপক্ষে s−mKs - mK অসম্ভব নোড রয়েছে
  • এই সীমাবদ্ধতা ব্যবহার করে সূচকীয় ছোট সম্ভাব্যতা সীমা অর্জন করা

প্রযুক্তিগত ফাংশন g(h,p)g(h,p):

  • সংজ্ঞা g(h,p)=p⋅exp⁡(−0.1hp1/h)g(h,p) = p \cdot \exp(-0.1h p^{1/h})
  • মূল নোড সীমাবদ্ধতা সেটে আছে/নেই এমন ক্ষেত্রে মূল অসমতা প্রমাণ করা
  • p=n−O(m)p = n^{-O(m)} এর সময় মান Chernoff সীমার চেয়ে আরও কঠোর

সমরূপ নর্মের বিশেষ চিকিত্সা

সমরূপ নর্মের জন্য, একটি ভিন্ন বিশ্লেষণ কৌশল গ্রহণ করা হয়:

  1. বিভাগ বিভাজন: ওজন 4−k4^{-k} দ্বারা নোডগুলিকে বিভাগ QkQ_k এ বিভক্ত করা
  2. ভাল-খারাপ পাতা শ্রেণীবিভাগ: kk-খারাপ পাতা সংজ্ঞা দেওয়া, তাদের অনুপাত সূচকীয়ভাবে ছোট প্রমাণ করা
  3. সরাসরি বিশ্লেষণ: জটিল লেবেল সিস্টেম এড়িয়ে, প্রত্যাশিত পুরস্কার সরাসরি বিশ্লেষণ করা

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

এই পেপারটি একটি বিশুদ্ধ তাত্ত্বিক কাজ, প্রধানত গাণিতিক প্রমাণের মাধ্যমে ফলাফল যাচাই করা হয়। পেপারটি প্রদান করে:

তাত্ত্বিক যাচাইকরণ

  1. নিম্ন সীমা মিলিত করা: বাইনারি XOS উদ্দেশ্যের জন্য, উপরের সীমা O(log⁡n/log⁡log⁡n)O(\log n/\log\log n) GNS17 এর নিম্ন সীমা Ω(log⁡n/log⁡log⁡n)\Omega(\log n/\log\log n) এর সাথে মিলিত
  2. পরামিতি নির্ভরতা: সীমার rr (সর্বাধিক প্রোবিং ক্রম দৈর্ঘ্য) এর উপর নির্ভরতা বিশ্লেষণ
  3. ধ্রুবক বিশ্লেষণ: সমরূপ নর্মের জন্য স্পষ্ট ধ্রুবক সীমা 2050 প্রদান করা

প্রযুক্তিগত যাচাইকরণ

  1. হ্রাস সঠিকতা: প্রতিটি হ্রাস ধাপের আনুমানিক অনুপাত বিশ্লেষণ
  2. অ্যালগরিদম জটিলতা: যদিও অ্যালগরিদম শুধুমাত্র বিশ্লেষণের জন্য ব্যবহৃত হয়, জটিলতা যুক্তিসঙ্গত
  3. পরামিতি নির্বাচন: K=O(log⁡n/log⁡log⁡n)K = O(\log n/\log\log n) এর সর্বোত্তমতা

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

প্রধান তাত্ত্বিক ফলাফল

উপপাদ্য 1.2 (সাধারণ মনোটোন নর্ম): অ্যাডাপটিভিটি গ্যাপ উপরের সীমা O(log⁡r⋅log⁡nlog⁡log⁡n)O\left(\log r \cdot \frac{\log n}{\log\log n}\right)

উপপাদ্য 1.3 (বাইনারি XOS উদ্দেশ্য): অ্যাডাপটিভিটি গ্যাপ Θ(log⁡nlog⁡log⁡n)\Theta\left(\frac{\log n}{\log\log n}\right) (কঠোর)

উপপাদ্য 1.4 (সমরূপ নর্ম): অ্যাডাপটিভিটি গ্যাপ O(1)O(1)

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

উন্নতির পরিমাণ:

  • সমরূপ নর্ম: O(log⁡n)O(\log n) PRS23 থেকে O(1)O(1) এ উন্নত
  • সাধারণ নর্ম: প্রথমবার মাল্টি-লগারিদমিক সীমা অর্জন, খোলা সমস্যা সমাধান
  • বাইনারি XOS: অ্যাসিম্পটোটিকভাবে কঠোর সীমা অর্জন

পদ্ধতি উদ্ভাবন:

  • গভীরতা নিয়ন্ত্রণের লেবেল সিস্টেম
  • উন্নত সম্ভাব্যতা বিশ্লেষণ কৌশল
  • একীভূত হ্রাস কাঠামো

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

ঐতিহাসিক উন্নয়ন

  1. প্রাথমিক কাজ: গুপ্তা-নাগারাজন GN13 বার্নুলি প্রোবিং প্রবর্তন করেছেন
  2. সাবমডিউলার ফাংশন: GNS16, GNS17 ধ্রুবক অ্যাডাপটিভিটি গ্যাপ প্রমাণ করেছেন
  3. XOS ফাংশন: GNS17 O(log⁡W)O(\log W) সীমা প্রমাণ করেছেন, যেখানে WW হল XOS প্রস্থ
  4. নর্ম উদ্দেশ্য: PRS23, KMS24 সমরূপ নর্ম এবং সুপারমডিউলার নর্ম অধ্যয়ন করেছেন

এই পেপারের অবস্থান

  • GNS17, KMS24 দ্বারা প্রস্তাবিত মূল অনুমান সমাধান করা
  • PRS23 দ্বারা সমরূপ নর্মের ফলাফল উন্নত করা
  • বিভিন্ন উদ্দেশ্য ফাংশন পরিচালনা করার জন্য একীভূত প্রযুক্তিগত কাঠামো প্রদান করা

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

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

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

সীমাবদ্ধতা

  1. ধ্রুবক ফ্যাক্টর: সমরূপ নর্মের ধ্রুবক 2050 বেশ বড়, যথেষ্ট কঠোর নাও হতে পারে
  2. log⁡r\log r ফাঁক: পরিচিত নিম্ন সীমার সাথে এখনও O(log⁡r)O(\log r) এর ফাঁক রয়েছে
  3. প্রযুক্তিগত জটিলতা: প্রমাণ কৌশল বেশ জটিল, অন্যান্য সমস্যায় প্রসারিত করা কঠিন হতে পারে

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

  1. সীমা কঠোর করা: নিম্ন সীমার সাথে ফাঁক কমানো
  2. ধ্রুবক উন্নত করা: সমরূপ নর্মের কঠোর ধ্রুবক অর্জন করা
  3. অ্যালগরিদম প্রয়োগ: অন্তর্দৃষ্টি আরও বিস্তৃত স্টোকাস্টিক সমন্বয় অপ্টিমাইজেশনে প্রয়োগ করা
  4. গণনামূলক জটিলতা: সর্বোত্তম কৌশল গণনার জটিলতা অধ্যয়ন করা

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

সুবিধা

প্রযুক্তিগত উদ্ভাবন:

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

তাত্ত্বিক অবদান:

  1. খোলা সমস্যা সমাধান: ক্ষেত্রের মূল অনুমান উত্তর দেওয়া
  2. কঠোর ফলাফল: বাইনারি XOS এর জন্য সর্বোত্তম সীমা অর্জন করা
  3. অপ্রত্যাশিত উন্নতি: সমরূপ নর্মের ধ্রুবক সীমা একটি অপ্রত্যাশিত শক্তিশালী ফলাফল

প্রযুক্তিগত গুণমান:

  1. প্রমাণ কঠোরতা: গাণিতিক যুক্তি স্পষ্ট এবং সম্পূর্ণ
  2. কাঠামো স্পষ্টতা: পেপার সংগঠন ভাল, বোঝা সহজ
  3. প্রযুক্তিগত গভীরতা: উন্নত সম্ভাব্যতা এবং সমন্বয় কৌশলের একাধিক ব্যবহার

অপূর্ণতা

প্রযুক্তিগত সীমাবদ্ধতা:

  1. জটিলতা: প্রমাণ কৌশল অত্যন্ত জটিল, আরও উন্নয়ন সীমিত করতে পারে
  2. ধ্রুবক সমস্যা: কিছু ধ্রুবক যথেষ্ট কঠোর নাও হতে পারে
  3. পরামিতি নির্ভরতা: rr এর উপর নির্ভরতা বিশ্লেষণ আরও গভীর হতে পারে

প্রয়োগ সীমাবদ্ধতা:

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

প্রভাব

একাডেমিক প্রভাব:

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

ব্যবহারিক মূল্য:

  1. অ্যালগরিদম ডিজাইন নির্দেশনা: বাস্তব অ্যালগরিদম ডিজাইনের জন্য তাত্ত্বিক সমর্থন প্রদান করা
  2. আনুমানিক গ্যারান্টি: সহজ কৌশলের কার্যকারিতা প্রমাণ করা
  3. প্রয়োগ ক্ষেত্র: মেশিন লার্নিং, অপারেশন গবেষণা ইত্যাদি ক্ষেত্রে সম্ভাব্য প্রয়োগ

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

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

সংদর্ভ

  • GNS17 গুপ্তা, নাগারাজন, সিংলা। "Adaptivity gaps for stochastic probing: submodular and XOS functions"
  • KMS24 কেসেলহেইম, মোলিনারো, সিংলা। "Supermodular approximation of norms and applications"
  • PRS23 প্যাটন, রুসো, সিংলা। "Submodular Norms with Applications To Online Facility Location and Stochastic Probing"

এই পেপারটি স্টোকাস্টিক সমন্বয় অপ্টিমাইজেশন ক্ষেত্রে গুরুত্বপূর্ণ তাত্ত্বিক অবদান করেছে, শুধুমাত্র একাধিক খোলা সমস্যা সমাধান করেনি বরং সাধারণ উদ্দেশ্য ফাংশন পরিচালনার জন্য নতুন প্রযুক্তিগত কাঠামো বিকাশ করেছে। যদিও প্রমাণ কৌশল বেশ জটিল, তবে এর তাত্ত্বিক মূল্য এবং ক্ষেত্রের অগ্রগতির প্রভাব উল্লেখযোগ্য।