[1] Garey M R, Johnson D S. Computers and Intractability [M]. San Francisco: W.H. Freeman Company, 1979. [2] Nakos V. Nearly optimal sparse polynomial multiplication [J]. IEEE Transactions on Information Theory, 2020, 66(11): 7231-7236. [3] Bringmann K, Fischer N, Nakos V. Sparse nonnegative convolution is equivalent to dense nonnegative convolution [C]//53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021: 1711-1724. [4] Sárközy A. Finite addition theorems, I [J]. Journal of Number Theory, 1989, 32(1): 114-130. [5] Sárközy A. Fine Addition Theorems, II [J]. Journal of Number Theory, 1994, 48(2): 197-218. [6] Lev V F. Blocks and progressions in subset sum sets [J]. Acta Arithmetica, 2003, 106(2): 123-142. [7] Szemerédi E, Vu V H. Finite and infinite arithmetic progressions in sumsets [J]. Annals of Mathematics, 2006, 163(1): 1-35. [8] Karp R M. Reducibility among combinatorial problems [M]//Miller R E, Thatcher J W, Bohlinger J D.(eds.)Complexity of Computer Computations, Boston: Springer, 1972: 85-103 [9] Bellman R. Dynamic Programming [M]. Princeton: Princeton University Press, 1957 [10] Pisinger D. Linear time algorithms for knapsack problems with bounded weights [J]. Journal of Algorithms, 1999, 33(1): 1-14. [11] Tamir A. New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems [J]. Operations Research Letters, 2009, 37(5): 303-306. [12] Kellerer H, Pferschy U. Improved dynamic programming in connection with an FPTAS for the knapsack problem [J]. Journal of Combinatorial Optimization, 2004, 8(1): 5-11. [13] Bateni M H, Hajiaghayi M T, Seddighin S, et al. Fast algorithms for knapsack via convolution and prediction [C]//50th Annual ACM SIGACT Symposium on Theory of Computing, 2018: 1269-1282. [14] Axiotis K, Tzamos C. Capacitated dynamic programming: Faster knapsack and graph algorithms [C]//46th International Colloquium on Automata, Languages, and Programming, 2019, 19: 1-13. [15] Eisenbrand F, Weismantel R. Proximity results and faster algorithms for integer programming using the Steinitz Lemma [J]. ACM Transactions on Algorithms, 2019, 16(1): 1-14. [16] Polak A, Rohwedder L, Wȩgrzycki K. knapsack and subset sum with small items [C]//48th International Colloquium on Automata, Languages, and Programming, 2021, 106: 1-19. [17] Bringmann K, Cassis A. Faster 0-1-knapsack via near-convex min-plus-convolution [C]//31st Annual European Symposium on Algorithms, 2023, 241-16. [18] Chen L, Lian J, Mao Y, et al. Faster algorithms for bounded knapsack and bounded subset sum via fine-grained proximity results [C]//35th Annual ACM-SIAM Symposium on Discrete Algorithms, 2024: 4828-4848. [19] Bringmann K. Knapsack with small items in near-quadratic time [C]//56th Annual ACM Symposium on Theory of Computing, 2024: 259-270. [20] Jin C. 0-1 knapsack in nearly quadratic time [C]//56th Annual ACM Symposium on Theory of Computing, 2024: 271-282. [21] Cygan M, Mucha M, Wȩgrzycki K, et al. On problems equivalent to (min,+)-convolution [J]. ACM Transactions on Algorithms, 2019, 15(1): 1-25. [22] Künnemann M, Paturi R, Schneider S. On the fine-grained complexity of one-dimensional dynamic programming [C]//44th International Colloquium on Automata, Languages, and Programming, 2017, 21: 1-15. [23] Sahni S. Approximate algorithms for the 0/1 knapsack problem [J]. Journal of the ACM, 1975, 22(1): 115-124. [24] Ibarra O H, Kim C E. Fast approximation algorithms for the knapsack and sum of subset problems [J]. Journal of the ACM,1975, 22(4): 463-468. [25] Lawler E L. Fast approximation algorithms for knapsack problems [J]. Mathematics of Operations Research, 1979, 4(4): 339-356. [26] Rhee D. Faster fully polynomial approximation schemes for knapsack problems [D]. Massachusetts Institute of Technology, 2015. [27] Chan T M. Approximation schemes for 0-1 knapsack [C]//1st Symposium on Simplicity in Algorithms, 2018, 5: 1-12. [28] Jin C. An improved FPTAS for 0-1 knapsack [C]//Proceedings of 46th International Colloquium on Automata, Languages, and Programming, 2019, 76: 1-14. [29] Deng M, Jin C, Mao X. Approximating knapsack and partition via dense subset sums [C]//34th Annual ACM-SIAM Symposium on Discrete Algorithms, 2023: 2961-2979. [30] Chen L, Lian J, Mao Y, et al. A nearly quadratic-time FPTAS for knapsack [C]//56th Annual ACM Symposium on Theory of Computing, 2024: 283-294. [31] Mao X. (1- ε)-approximation of knapsack in nearly quadratic time [C]//56th Annual ACM Symposium on Theory of Computing, 2024: 295-306. [32] Vazirani V V. Approximation Algorithms [M]. Heidelberg: Springer, 2001 [33] Aggarwal A, Klawe M M, Moran S, et al. Geometric applications of a matrix-searching algorithm [J]. Algorithmica, 1987, 2(1): 195-208. [34] Bringmann K, Wellnitz P. On near-linear-time algorithms for dense subset sum [C]//2nd ACMSIAM Symposium on Discrete Algorithms, 2021: 1777-1796. [35] Szemerédi E, Vu V. Long arithmetic progressions in sumsets: Thresholds and bounds [J]. Journal of the American Mathematical Society, 2005, 19(1): 119-169. [36] Bringmann K, Nakos V. A Fine-Grained perspective on approximating subset sum and partition [C]//32nd ACM-SIAM Symposium on Discrete Algorithms, 2021: 1797-1815. [37] Abboud A, Bringmann K, Hermelin D, et al. SETH-based lower bounds for subset sum and bicriteria path [J]. ACM Transactions on Algorithms, 2022, 18(1): 1-22. [38] Gens G V, Levner E V. Fast approximation algorithms for knapsack type problems [C]//Optimization Techniques, Lecture Notes in Control and Information Sciences, 1980: 185- 194. [39] Mucha M, Wȩgrzycki K, W lodarczyk M. A Subquadratic Approximation Scheme for Partition [C]//30th Annual ACM-SIAM Symposium on Discrete Algorithms, 2019: 70-88. [40] Wu X, Chen L. Improved approximation schemes for (un-)bounded subset-sum and partition [EB/OL]. [2025-03-14]. arXiv:221202883 [41] Chen L, Lian J, Mao Y, et al. Approximating partition in near-linear time [C]//56th Annual ACM Symposium on Theory of Computing, 2024: 307-318. [42] Karp R M. The fast approximate solution of hard combinatorial problems [C]//6th SouthEastern Conf Combinatorics, Graph Theory and Computing, 1975: 15-31. [43] Gens G V, Levner E V. Approximation algorithm for some scheduling problems [J]. Engrg Cybernetics, 1978, 6: 38-46. [44] Gens G V, Levner E V. Computational complexity of approximation algorithms for combinatorial problems [C]//International Symposium on Mathematical Foundations of Computer Science, 1979. [45] Chen L, Lian J, Mao Y, et al. An improved pseudopolynomial time algorithm for subset sum [C]//65th Symposium on Foundations of Computer Science, 2024. [46] Freıman G A. Foundations of a Structual Theory of Set Addition [M]. Providence: American Mathematical Society, 1973. [47] Tao T, Vu V H. Additive Combinatorics [M]. Cambridge: Cambridge University Press, 2006. [48] Balog A, Szemerédi E. A statistical theorem of set addition [J]. Combinatorica, 1994, 14(3): 263-268. [49] Gowers W T. A new proof of Szemerédi’s theorem [J]. Geometric & Functional Analysis GAFA, 2001, 11(3): 465-588. [50] Balog A. Many additive quadruples [C]//Proceedings and Lecture Notes in Additive Combinatorics,2007, 43: 10. [51] Sudakov B, Szemerédi E, Vu V. On a question of erdos and moser [J]. Duke Mathematical Journal, 2005, 126(1): 129-155. [52] Bremner D, Chan T M, Demaine E D, et al. Necklaces, convolutions, and x + y [C]//14th Annual European Symposium, 2006: 160-171. [53] Williams R. Faster all-pairs shortest paths via circuit complexity [C]//46th annual ACM symposium on Theory of computing, 2014: 664-673. [54] Chan T M, Lewenstein M. Clustered integer 3SUM via additive combinatorics [C]//47th annual ACM symposium on Theory of computing, 2015: 31-40. [55] Chi S, Duan R, Xie T, et al. Faster min-plus product for monotone instances [C]//54th Annual ACM SIGACT Symposium on Theory of Computing, 2022: 1529-1542. [56] He Q, Xu Z. Simple and faster algorithms for knapsack [C]//7th Symposium on Simplicity in Algorithms, 2024: 56-62. [57] Bringmann K. A near-linear pseudopolynomial time algorithm for subset sum [C]//28th Annual ACM-SIAM Symposium on Discrete Algorithms, 2017: 1073-1084. [58] Kellerer H, Mansini R, Pferschy U, et al. An efficient fully polynomial approximation scheme for the Subset-Sum Problem [J]. Journal of Computer and System Sciences, 2003, 66(2): 349-370. [59] Bringmann K, Dürr A, Polak A. Even faster knapsack via rectangular monotone min-plus convolution and balancing [C]//32nd Annual European Symposium on Algorithms, 2024, 33: 1-15. |