Scholarlink

<p>We investigate pseudo-polynomial time algorithms for Subset Sum. Given a multi-set <i>X</i> consisting of <i>n</i> positive integers and a target <i>t</i>, Subset Sum asks whether some subset of <i>X</i> sums to <i>t</i>. Bringmann proposed an <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\widetilde{O}(n + t)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover accent="true"> <mi>O</mi> <mo stretchy="false">~</mo> </mover> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mi>t</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>-time algorithm [Bringmann SODA’17]. An open question has naturally arisen: can Subset Sum be solved in <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(O(n + w)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mi>w</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time? Here <i>w</i> is the largest integer in <i>X</i>. We make progress towards resolving the open question by proposing an <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\widetilde{O}(n + \sqrt{wt})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mover accent="true"> <mi>O</mi> <mo stretchy="false">~</mo> </mover> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <msqrt> <mrow> <mi mathvariant="italic">wt</mi> </mrow> </msqrt> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>-time algorithm.</p>

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

An Improved Pseudopolynomial Time Algorithm for Subset Sum

  • 期刊论文

  • 发表日期：

    2026年3月10日

查看全文
  • Lin Chen,
  • Jiayi Lian,
  • Yuchen Mao,
  • Guochuan Zhang

摘要

We investigate pseudo-polynomial time algorithms for Subset Sum. Given a multi-set X consisting of n positive integers and a target t, Subset Sum asks whether some subset of X sums to t. Bringmann proposed an \(\widetilde{O}(n + t)\) O ~ ( n + t ) -time algorithm [Bringmann SODA’17]. An open question has naturally arisen: can Subset Sum be solved in \(O(n + w)\) O ( n + w ) time? Here w is the largest integer in X. We make progress towards resolving the open question by proposing an \(\widetilde{O}(n + \sqrt{wt})\) O ~ ( n + wt ) -time algorithm.