Scholarlink

<p>Many applications such as Text Summarization, Sensor Placement and Revenue Maximization fall into a general setting: the problem of maximizing a non-monotone DR-submodular function subject to a knapsack constraint on the integer lattice. We consider this problem in the streaming model. By embedding a new binary search into threshold greedy, we propose three streaming algorithms with the corresponding performance guarantees: one-pass <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10288_2025_593_Article_IEq1.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">\((\frac{1}{8}-\epsilon )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mfrac> <mn>1</mn> <mn>8</mn> </mfrac> <mo>-</mo> <mi>ϵ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-approximation streaming algorithm, two-pass <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10288_2025_593_Article_IEq2.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">\((\frac{1}{6}-\epsilon )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mfrac> <mn>1</mn> <mn>6</mn> </mfrac> <mo>-</mo> <mi>ϵ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-approximation streaming algorithm, and one-pass <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10288_2025_593_Article_IEq3.gif" Format="GIF" Height="27" Rendition="HTML" Resolution="72" Type="Linedraw" Width="93" /> </InlineMediaObject> <EquationSource Format="TEX">\((\frac{\beta (r-1)}{r-1+3r\beta }-\epsilon )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mfrac> <mrow> <mi>β</mi> <mo stretchy="false">(</mo> <mi>r</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mrow> <mi>r</mi> <mo>-</mo> <mn>1</mn> <mo>+</mo> <mn>3</mn> <mi>r</mi> <mi>β</mi> </mrow> </mfrac> <mo>-</mo> <mi>ϵ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-approximation streaming algorithm. Furthermore, we can also guarantee that our algorithms run in nearly-linear time in the number of nodes and obtain theoretically guaranteed results for Revenue Maximization.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Streaming algorithms for non-monotone DR-submodular maximization under a knapsack constraint on the integer lattice

  • 期刊论文

  • 发表日期：

    2025年8月7日

查看全文
  • Hongyang Zhang,
  • Wenchang Luo

摘要

Many applications such as Text Summarization, Sensor Placement and Revenue Maximization fall into a general setting: the problem of maximizing a non-monotone DR-submodular function subject to a knapsack constraint on the integer lattice. We consider this problem in the streaming model. By embedding a new binary search into threshold greedy, we propose three streaming algorithms with the corresponding performance guarantees: one-pass \((\frac{1}{8}-\epsilon )\) ( 1 8 - ϵ ) -approximation streaming algorithm, two-pass \((\frac{1}{6}-\epsilon )\) ( 1 6 - ϵ ) -approximation streaming algorithm, and one-pass \((\frac{\beta (r-1)}{r-1+3r\beta }-\epsilon )\) ( β ( r - 1 ) r - 1 + 3 r β - ϵ ) -approximation streaming algorithm. Furthermore, we can also guarantee that our algorithms run in nearly-linear time in the number of nodes and obtain theoretically guaranteed results for Revenue Maximization.