pith. sign in

arxiv: 2402.14493 · v3 · submitted 2024-02-22 · 💻 cs.DS

An Improved Pseudopolynomial Time Algorithm for Subset Sum

Lin Chen , Jiayi Lian , Yuchen Mao , Guochuan Zhang This is my paper

Pith reviewed 2026-05-24 04:00 UTC · model grok-4.3

classification 💻 cs.DS
keywords Subset Sumpseudo-polynomial timealgorithm complexitydynamic programmingword-RAM model
0
0 comments X

The pith

Subset Sum admits an Õ(n + √(wt))-time algorithm, advancing the open question of O(n + w) solvability.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines pseudo-polynomial algorithms for deciding whether a subset of n positive integers sums to a target t. Prior work gave an Õ(n + t) algorithm and left open whether O(n + w) time is possible, with w the largest input integer. The authors give an Õ(n + √(wt)) algorithm that improves the dependence on t whenever w is not too large. This constitutes measurable progress on the open question while remaining within the standard word-RAM model. A positive resolution of the open question would make many subset-sum instances tractable even when the target is enormous.

Core claim

The authors propose an Õ(n + √(wt))-time algorithm for Subset Sum. This improves upon the Õ(n + t) algorithm by Bringmann and makes progress on whether Subset Sum can be solved in O(n + w) time.

What carries the argument

An improved pseudo-polynomial algorithm achieving Õ(n + √(wt)) running time for Subset Sum.

If this is right

  • Subset Sum instances become solvable faster whenever w is much smaller than t.
  • The gap between known upper bounds and the O(n + w) target is narrowed.
  • The same approach may yield improved bounds for related problems such as the knapsack problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The square-root dependence hints that hardness may track the geometric mean of w and t.
  • Further refinements could close the remaining gap to an O(n + w) algorithm.

Load-bearing premise

The claimed running time holds under the standard word-RAM model with unit-cost arithmetic on word-sized integers.

What would settle it

An explicit implementation of the algorithm on a concrete input whose measured running time exceeds Õ(n + √(wt)) would falsify the stated bound.

read the original abstract

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

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript claims an Õ(n + √(wt))-time algorithm for Subset Sum on a multi-set of n positive integers with maximum element w and target t. It improves on Bringmann's Õ(n + t) algorithm and makes progress toward the open O(n + w) question via an optimized dynamic-programming procedure that partitions instances by element magnitudes and solves subproblems using table lookups and limited FFT-style convolutions.

Significance. If the stated running time holds, the result is a meaningful incremental advance in pseudopolynomial algorithms for Subset Sum. The construction is internally consistent: the recurrence and data-structure bounds close without hidden polynomial dependence on t or w beyond the Õ notation, and the reduction to the standard word-RAM model with unit-cost word operations aligns with prior cited work.

minor comments (3)
  1. Abstract: the claim is stated without any recurrence, data-structure outline, or proof sketch; while the body supplies these, a one-sentence high-level description in the abstract would improve accessibility.
  2. §1 (Introduction): the open question is phrased as 'can Subset Sum be solved in O(n + w) time?'; clarify whether this is conjectured to be possible or merely an aspirational target.
  3. Notation: the Õ notation is used throughout; explicitly define it (including the precise polylog factors hidden) on first use.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and the positive assessment of our result as a meaningful incremental advance. The recommendation for minor revision is noted; we will incorporate any editorial suggestions in the revised version.

Circularity Check

0 steps flagged

No circularity; direct algorithmic construction from standard primitives

full rationale

The manuscript presents an explicit dynamic-programming algorithm that partitions the input by element magnitude, solves subproblems via table lookups and bounded convolutions, and closes the recurrence under the standard word-RAM model with unit-cost word operations. No parameter is fitted to data and then re-used as a prediction; no self-citation supplies a uniqueness theorem or ansatz that the present derivation depends upon; the claimed Õ(n + √(wt)) bound follows from the size of the constructed tables and the cost of the convolutions, none of which are defined in terms of the final running time. The cited Bringmann SODA'17 result is external prior work and is not required for the correctness of the new construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available, so the ledger is necessarily incomplete. No free parameters or invented entities are visible. The sole identifiable axiom is the standard word-RAM model used for all pseudo-polynomial analyses.

axioms (1)
  • domain assumption Arithmetic operations on word-sized integers take unit time (word-RAM model).
    Standard background assumption for all time-complexity claims in the cited literature.

pith-pipeline@v0.9.0 · 5636 in / 1086 out tokens · 26659 ms · 2026-05-24T04:00:58.621600+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

51 extracted references · 51 canonical work pages · 1 internal anchor

  1. [1]

    SETH-based Lower Bounds for Subset Sum and Bicriteria Path

    Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay. SETH-based Lower Bounds for Subset Sum and Bicriteria Path . ACM Transactions on Algorithms , 18(1):1--22, January 2022. https://doi.org/10.1145/3450524 doi:10.1145/3450524

    work page doi:10.1145/3450524 2022

  2. [2]

    Fast modular subset sum using linear sketching

    Kyriakos Axiotis, Arturs Backurs, Ce Jin, Christos Tzamos, and Hongxun Wu. Fast modular subset sum using linear sketching. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019) , pages 58--69. SIAM, 2019. https://doi.org/10.1137/1.9781611975482.4 doi:10.1137/1.9781611975482.4

    work page doi:10.1137/1.9781611975482.4 2019

  3. [3]

    N. Alon. Subset sums. Journal of Number Theory , 27(2):196--205, October 1987. https://doi.org/10.1016/0022-314X(87)90061-8 doi:10.1016/0022-314X(87)90061-8

    work page doi:10.1016/0022-314x(87)90061-8 1987

  4. [4]

    Andrew Arnold and Daniel S. Roche. Output- Sensitive Algorithms for Sumset and Sparse Polynomial Multiplication . In Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation ( ISSAC 2015) , pages 29--36, New York, USA , June 2015. https://doi.org/10.1145/2755996.2756653 doi:10.1145/2755996.2756653

    work page doi:10.1145/2755996.2756653 2015

  5. [5]

    Capacitated Dynamic Programming : Faster Knapsack and Graph Algorithms

    Kyriakos Axiotis and Christos Tzamos. Capacitated Dynamic Programming : Faster Knapsack and Graph Algorithms . In 46th International Colloquium on Automata , Languages , and Programming ( ICALP 2019) , volume 132, pages 19:1--19:13, Dagstuhl, Germany , 2019. https://doi.org/10.4230/LIPIcs.ICALP.2019.19 doi:10.4230/LIPIcs.ICALP.2019.19

    work page doi:10.4230/lipics.icalp.2019.19 2019

  6. [6]

    Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution

    Karl Bringmann and Alejandro Cassis. Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution . In 49th International Colloquium on Automata , Languages , and Programming ( ICALP 2022) , volume 229, pages 31:1--31:21, Dagstuhl, Germany , 2022. https://doi.org/10.4230/LIPIcs.ICALP.2022.31 doi:10.4230/LIPIcs.ICALP.2022.31

    work page doi:10.4230/lipics.icalp.2022.31 2022

  7. [7]

    Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution

    Karl Bringmann and Alejandro Cassis. Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution . In 31st Annual European Symposium on Algorithms (ESA 2023) , volume 274, pages 24:1--24:16, Dagstuhl, Germany, 2023. https://doi.org/10.4230/LIPIcs.ESA.2023.24 doi:10.4230/LIPIcs.ESA.2023.24

    work page doi:10.4230/lipics.esa.2023.24 2023

  8. [8]

    Dynamic Programming , volume 33

    Richard Bellman. Dynamic Programming , volume 33. Princeton University Press , 1957. http://arxiv.org/abs/j.ctv1nxcw0f arXiv:j.ctv1nxcw0f , https://doi.org/10.2307/j.ctv1nxcw0f doi:10.2307/j.ctv1nxcw0f

    work page doi:10.2307/j.ctv1nxcw0f 1957

  9. [9]

    Sparse nonnegative convolution is equivalent to dense nonnegative convolution

    Karl Bringmann, Nick Fischer, and Vasileios Nakos. Sparse nonnegative convolution is equivalent to dense nonnegative convolution. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021) , pages 1711--1724, Virtual Italy , June 2021. https://doi.org/10.1145/3406325.3451090 doi:10.1145/3406325.3451090

    work page doi:10.1145/3406325.3451090 2021

  10. [10]

    Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution

    Karl Bringmann, Nick Fischer, and Vasileios Nakos. Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution . In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms ( SODA 2022) , Proceedings, pages 3069--3090, January 2022. https://doi.org/10.1137/1.9781611977073.119 doi:10.1137/1.9781611977073.119

    work page doi:10.1137/1.9781611977073.119 2022

  11. [11]

    Fast algorithms for knapsack via convolution and prediction

    MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Saeed Seddighin, and Cliff Stein. Fast algorithms for knapsack via convolution and prediction. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing ( STOC 2018) , pages 1269--1282, New York, NY, USA , June 2018. https://doi.org/10.1145/3188745.3188876 doi:10.1145/3188745.3188876

    work page doi:10.1145/3188745.3188876 2018

  12. [12]

    Top-k-convolution and the quest for near-linear output-sensitive subset sum

    Karl Bringmann and Vasileios Nakos. Top-k-convolution and the quest for near-linear output-sensitive subset sum. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing ( STOC 2020) , pages 982--995, 2020. https://doi.org/10.1145/3357713.3384308 doi:10.1145/3357713.3384308

    work page doi:10.1145/3357713.3384308 2020

  13. [13]

    Fast n- Fold Boolean Convolution via Additive Combinatorics

    Karl Bringmann and Vasileios Nakos. Fast n- Fold Boolean Convolution via Additive Combinatorics . In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) , 2021. https://doi.org/10.4230/LIPIcs.ICALP.2021.41 doi:10.4230/LIPIcs.ICALP.2021.41

    work page doi:10.4230/lipics.icalp.2021.41 2021

  14. [14]

    A Fine-Grained Perspective on Approximating Subset Sum and Partition

    Karl Bringmann and Vasileios Nakos. A Fine-Grained Perspective on Approximating Subset Sum and Partition . In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms ( SODA 2021) , Proceedings, pages 1797--1815, January 2021. https://doi.org/10.1137/1.9781611976465.108 doi:10.1137/1.9781611976465.108

    work page doi:10.1137/1.9781611976465.108 2021

  15. [15]

    A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum

    Karl Bringmann. A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum . In Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms ( SODA 2017) , pages 1073--1084, January 2017. https://doi.org/10.1137/1.9781611974782.69 doi:10.1137/1.9781611974782.69

    work page doi:10.1137/1.9781611974782.69 2017

  16. [16]

    Knapsack with Small Items in Near-Quadratic Time , September 2023

    Karl Bringmann. Knapsack with Small Items in Near-Quadratic Time , September 2023. To Appear in STOC 2024. http://arxiv.org/abs/2308.03075 arXiv:2308.03075

    work page arXiv 2023

  17. [17]

    A statistical theorem of set addition

    Antal Balog and Endre Szemer \'e di. A statistical theorem of set addition. Combinatorica , 14(3):263--268, 1994. https://doi.org/10.1007/BF01212974 doi:10.1007/BF01212974

    work page doi:10.1007/bf01212974 1994

  18. [18]

    On Near-Linear-Time Algorithms for Dense Subset Sum

    Karl Bringmann and Philip Wellnitz. On Near-Linear-Time Algorithms for Dense Subset Sum . In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms ( SODA 2021) , pages 1777--1796, January 2021. https://doi.org/10.1137/1.9781611976465.107 doi:10.1137/1.9781611976465.107

    work page doi:10.1137/1.9781611976465.107 2021

  19. [19]

    Solving dense subset-sum problems by using analytical number theory

    Mark Chaimovich, Gregory Freiman, and Zvi Galil. Solving dense subset-sum problems by using analytical number theory. Journal of Complexity , 5(3):271--282, 1989

    work page 1989

  20. [20]

    Solving dense subset-sum problems by using analytical number theory

    Mark Chaimovich, Gregory Freiman, and Zvi Galil. Solving dense subset-sum problems by using analytical number theory. Journal of Complexity , 5(3):271--282, September 1989. https://doi.org/10.1016/0885-064X(89)90025-3 doi:10.1016/0885-064X(89)90025-3

    work page doi:10.1016/0885-064x(89)90025-3 1989

  21. [21]

    Verifying candidate matches in sparse and wildcard matching

    Richard Cole and Ramesh Hariharan. Verifying candidate matches in sparse and wildcard matching. In Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing ( STOC 2002) , pages 592--601, New York, NY, USA , May 2002. https://doi.org/10.1145/509907.509992 doi:10.1145/509907.509992

    work page doi:10.1145/509907.509992 2002

  22. [22]

    New algorithm for dense subset-sum problem

    Mark Chaimovich. New algorithm for dense subset-sum problem. Ast \'e risque , 258:363--373, 1999

    work page 1999

  23. [23]

    Chan and Moshe Lewenstein

    Timothy M. Chan and Moshe Lewenstein. Clustered Integer 3SUM via Additive Combinatorics . In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing ( STOC 2015) , pages 31--40, New York, NY, USA , June 2015. https://doi.org/10.1145/2746539.2746568 doi:10.1145/2746539.2746568

    work page doi:10.1145/2746539.2746568 2015

  24. [24]

    Approximating partition in near-linear time, 2024

    Lin Chen, Jiayi Lian, Yuchen Mao, and Guochuan Zhang. Approximating partition in near-linear time, 2024. To Appear in STOC 2024. http://arxiv.org/abs/2402.11426 arXiv:2402.11426

    work page arXiv 2024

  25. [25]

    Faster algorithms for bounded knapsack and bounded subset sum via fine-grained proximity results

    Lin Chen, Jiayi Lian, Yuchen Mao, and Guochuan Zhang. Faster algorithms for bounded knapsack and bounded subset sum via fine-grained proximity results. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024) , pages 4828--4848. SIAM, 2024. https://doi.org/10.1137/1.9781611977912.171 doi:10.1137/1.9781611977912.171

    work page doi:10.1137/1.9781611977912.171 2024

  26. [26]

    Approximating Knapsack and Partition via Dense Subset Sums

    Mingyang Deng, Ce Jin, and Xiao Mao. Approximating Knapsack and Partition via Dense Subset Sums . In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms ( SODA 2023) , Proceedings, pages 2961--2979, January 2023. https://doi.org/10.1137/1.9781611977554.ch113 doi:10.1137/1.9781611977554.ch113

    work page doi:10.1137/1.9781611977554.ch113 2023

  27. [27]

    An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem

    Zvi Galil and Oded Margalit. An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem . SIAM Journal on Computing , 20(6):1157--1189, December 1991. https://doi.org/10.1137/0220072 doi:10.1137/0220072

    work page doi:10.1137/0220072 1991

  28. [28]

    A new proof of szemer \'e di's theorem

    William T Gowers. A new proof of szemer \'e di's theorem. Geometric & Functional Analysis GAFA , 11(3):465--588, 2001. https://doi.org/10.1007/s00039-001-0332-9 doi:10.1007/s00039-001-0332-9

    work page doi:10.1007/s00039-001-0332-9 2001

  29. [29]

    Probability Inequalities for Sums of Bounded Ra n- dom Variables

    Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association , 58(301):13--30, 1963. https://doi.org/10.1080/01621459.1963.10500830 doi:10.1080/01621459.1963.10500830

    work page doi:10.1080/01621459.1963.10500830 1963

  30. [30]

    Simple and faster algorithms for knapsack

    Qizheng He and Zhean Xu. Simple and faster algorithms for knapsack. In Proceedings of 2024 Symposium on Simplicity in Algorithms (SOSA 2024) , pages 56--62, 2024. https://doi.org/10.1137/1.9781611977936.6 doi:10.1137/1.9781611977936.6

    work page doi:10.1137/1.9781611977936.6 2024

  31. [31]

    Ibarra and Chul E

    Oscar H. Ibarra and Chul E. Kim. Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems . Journal of the ACM , 22(4):463--468, 1975. https://doi.org/10.1145/321906.321909 doi:10.1145/321906.321909

    work page doi:10.1145/321906.321909 1975

  32. [32]

    0-1 Knapsack in Nearly Quadratic Time , August 2023

    Ce Jin. 0-1 Knapsack in Nearly Quadratic Time , August 2023. To Appear in STOC 2024. http://arxiv.org/abs/2308.04093 arXiv:2308.04093

    work page arXiv 2023

  33. [33]

    On integer programming, discrepancy, and convolution

    Klaus Jansen and Lars Rohwedder. On integer programming, discrepancy, and convolution. Mathematics of Operations Research , 48(3):1481--1495, 2023. https://doi.org/10.1287/moor.2022.1308 doi:10.1287/moor.2022.1308

    work page doi:10.1287/moor.2022.1308 2023

  34. [34]

    A simple near-linear pseudopolynomial time randomized algorithm for subset sum

    Ce Jin and Hongxun Wu. A simple near-linear pseudopolynomial time randomized algorithm for subset sum. In Proceedings of 2nd Symposium on Simplicity in Algorithms ( SOSA 2019) , volume 69, pages 17:1--17:6, 2019. https://doi.org/10.4230/OASICS.SOSA.2019.17 doi:10.4230/OASICS.SOSA.2019.17

    work page doi:10.4230/oasics.sosa.2019.17 2019

  35. [35]

    Richard M. Karp. Reducibility among Combinatorial Problems , pages 85--103. Springer US , Boston, MA , 1972. https://doi.org/10.1007/978-1-4684-2001-2_9 doi:10.1007/978-1-4684-2001-2_9

    work page doi:10.1007/978-1-4684-2001-2_9 1972

  36. [36]

    The fast approximate solution of hard combinatorial problems

    Richard M Karp. The fast approximate solution of hard combinatorial problems. In Proc. 6th South-Eastern Conf. Combinatorics, Graph Theory and Computing (Florida Atlantic U. 1975) , pages 15--31, 1975

    work page 1975

  37. [37]

    On the fine-grained complexity of the unbounded subsetsum and the frobenius problem

    Kim-Manuel Klein. On the fine-grained complexity of the unbounded subsetsum and the frobenius problem. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022) , pages 3567--3582. SIAM, 2022. https://doi.org/10.1137/1.9781611977073.141 doi:10.1137/1.9781611977073.141

    work page doi:10.1137/1.9781611977073.141 2022

  38. [38]

    An efficient approximation scheme for the subset-sum problem

    Hans Kellerer, Ulrich Pferschy, and Maria Grazia Speranza. An efficient approximation scheme for the subset-sum problem. In Hon Wai Leong, Hiroshi Imai, and Sanjay Jain, editors, Algorithms and Computation , Lecture Notes in Computer Science , pages 394--403, Berlin, Heidelberg , 1997. https://doi.org/10.1007/3-540-63890-3_42 doi:10.1007/3-540-63890-3_42

    work page doi:10.1007/3-540-63890-3_42 1997

  39. [39]

    A faster pseudopolynomial time algorithm for subset sum

    Konstantinos Koiliaris and Chao Xu. A faster pseudopolynomial time algorithm for subset sum. In Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) , pages 1062--1072, 2017. https://doi.org/10.1137/1.9781611974782.68 doi:10.1137/1.9781611974782.68

    work page doi:10.1137/1.9781611974782.68 2017

  40. [40]

    Subset Sum Made Simple

    Konstantinos Koiliaris and Chao Xu. Subset Sum Made Simple , July 2018. http://arxiv.org/abs/1807.08248 arXiv:1807.08248

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  41. [41]

    A Subquadratic Approximation Scheme for Partition

    Marcin Mucha, Karol W e grzycki, and Micha W odarczyk. A Subquadratic Approximation Scheme for Partition . In Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms ( SODA 2019) , Proceedings, pages 70--88, January 2019. https://doi.org/10.1137/1.9781611975482.5 doi:10.1137/1.9781611975482.5

    work page doi:10.1137/1.9781611975482.5 2019

  42. [42]

    Nearly Optimal Sparse Polynomial Multiplication

    Vasileios Nakos. Nearly Optimal Sparse Polynomial Multiplication . IEEE Transactions on Information Theory , 66(11):7231--7236, November 2020. https://doi.org/10.1109/TIT.2020.2989385 doi:10.1109/TIT.2020.2989385

    work page doi:10.1109/tit.2020.2989385 2020

  43. [43]

    Linear Time Algorithms for Knapsack Problems with Bounded Weights

    David Pisinger. Linear Time Algorithms for Knapsack Problems with Bounded Weights . Journal of Algorithms , 33(1):1--14, October 1999. https://doi.org/10.1006/jagm.1999.1034 doi:10.1006/jagm.1999.1034

    work page doi:10.1006/jagm.1999.1034 1999

  44. [44]

    Dynamic programming on the word ram

    Pisinger. Dynamic programming on the word ram. Algorithmica , 35:128--145, 2003. https://doi.org/10.1007/s00453-002-0989-y doi:10.1007/s00453-002-0989-y

    work page doi:10.1007/s00453-002-0989-y 2003

  45. [45]

    Knapsack and Subset Sum with Small Items

    Adam Polak, Lars Rohwedder, and Karol W e grzycki. Knapsack and Subset Sum with Small Items . In 48th International Colloquium on Automata , Languages , and Programming ( ICALP 2021) , volume 198, pages 106:1--106:19, Dagstuhl, Germany , 2021. https://doi.org/10.4230/LIPIcs.ICALP.2021.106 doi:10.4230/LIPIcs.ICALP.2021.106

    work page doi:10.4230/lipics.icalp.2021.106 2021

  46. [46]

    S \'a rk \"o zy

    A. S \'a rk \"o zy. Finite addition theorems, I . Journal of Number Theory , 32(1):114--130, May 1989. https://doi.org/10.1016/0022-314X(89)90102-9 doi:10.1016/0022-314X(89)90102-9

    work page doi:10.1016/0022-314x(89)90102-9 1989

  47. [47]

    S \'a rk \"o zy

    A. S \'a rk \"o zy. Fine Addition Theorems , II . Journal of Number Theory , 48(2):197--218, August 1994. https://doi.org/10.1006/jnth.1994.1062 doi:10.1006/jnth.1994.1062

    work page doi:10.1006/jnth.1994.1062 1994

  48. [48]

    Szemer \'e di and V

    E. Szemer \'e di and V. Vu. Long arithmetic progressions in sumsets: Thresholds and bounds. Journal of the American Mathematical Society , 19(1):119--169, September 2005. https://doi.org/10.1090/S0894-0347-05-00502-3 doi:10.1090/S0894-0347-05-00502-3

    work page doi:10.1090/s0894-0347-05-00502-3 2005

  49. [49]

    Szemer \'e di and V

    E. Szemer \'e di and V. H. Vu. Finite and Infinite Arithmetic Progressions in Sumsets . Annals of Mathematics , 163(1):1--35, 2006. URL: https://www.jstor.org/stable/20159950

    work page arXiv 2006

  50. [50]

    New pseudopolynomial complexity bounds for the bounded and other integer Knapsack related problems

    Arie Tamir. New pseudopolynomial complexity bounds for the bounded and other integer Knapsack related problems. Operations Research Letters , 37(5):303--306, 2009. https://doi.org/10.1016/j.orl.2009.05.003 doi:10.1016/j.orl.2009.05.003

    work page doi:10.1016/j.orl.2009.05.003 2009

  51. [51]

    Improved Approximation Schemes for ( Un- ) Bounded Subset-Sum and Partition , December 2022

    Xiaoyu Wu and Lin Chen. Improved Approximation Schemes for ( Un- ) Bounded Subset-Sum and Partition , December 2022. http://arxiv.org/abs/2212.02883 arXiv:2212.02883

    work page arXiv 2022