中文

Operations Research Transactions >

2025 , Vol. 29 >Issue 3: 202 - 222

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2025.03.010

Research Article

Application of additive combinatorics in several classic combinatorial optimization problems

  • Lin CHEN
Expand
  • 1. College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, Zhejiang, China

Received date: 2025-03-03

  Online published: 2025-09-09

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.
Fold

Abstract

We investigate fundamental combinatorial optimization problems, including the knapsack problem, the subset sum problem and the convolution problem. We want to explore algorithms that achieve the best possible running time, that is, algorithms whose running time is the best possible under standard complexity assumptions. In recent years, important algorithmic progress has been achieved in classic combinatorial optimization problems via additive combinatorics tools. In particular, for several variants of the knapsack problem and subset sum problem researchers have obtained pseudopolynomial time algorithms and polynomial time approximation schemes whose running time almost matches their lower bounds. This paper will survey several important results along this research line, showing the relevance between additive combinatorics and discrete optimization. In particular, we will present: (ⅰ) the finite addition theorem and its application in the algorithmic design for the knapsack problem and the subset sum problem; (ⅱ) Szemerédi-Vu sumset theorem and its application in the algorithmic design for the subset sum problem; and (ⅲ) Balog-Szemerédi-Gowers theorem and its application in the algorithmic design for the bounded monotone (min, +)-convolution problem.

Key words： pseudopolynomial time algorithm; polynomial time approximation scheme; knapsack; subset sum; additive combinatorics

Cite this article

Lin CHEN . Application of additive combinatorics in several classic combinatorial optimization problems[J]. Operations Research Transactions, 2025 , 29(3) : 202 -222 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.03.010

References

1 GareyM R,JohnsonD S.Computers and Intractability[M].San Francisco:W.H. Freeman Company,1979.
2 NakosV.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?zyA.Finite addition theorems, Ⅰ[J].Journal of Number Theory,1989,32(1):114-130.
5 Sárk?zyA.Fine Addition Theorems, Ⅱ[J].Journal of Number Theory,1994,48(2):197-218.
6 LevV F.Blocks and progressions in subset sum sets[J].Acta Arithmetica,2003,106(2):123-142.
7 SzemerédiE,VuV 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 BellmanR.Dynamic Programming[M].Princeton:Princeton University Press,1957.
10 PisingerD.Linear time algorithms for knapsack problems with bounded weights[J].Journal of Algorithms,1999,33(1):1-14.
11 TamirA.New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems[J].Operations Research Letters,2009,37(5):303-306.
12 KellererH,PferschyU.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 EisenbrandF,WeismantelR.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]//31 st Annual European Symposium on Algorithms, 2023, 24 1-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 CyganM,MuchaM,W?grzyckiK,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 SahniS.Approximate algorithms for the 0/1 knapsack problem[J].Journal of the ACM,1975,22(1):115-124.
24 IbarraO H,KimC E.Fast approximation algorithms for the knapsack and sum of subset problems[J].Journal of the ACM,1975,22(4):463-468.
25 LawlerE 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 VaziraniV V.Approximation Algorithms[M].Heidelberg:Springer,2001.
33 AggarwalA,KlaweM M,MoranS,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 ACM-SIAM Symposium on Discrete Algorithms, 2021: 1777-1796.
35 SzemerédiE,VuV.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 AbboudA,BringmannK,HermelinD,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?odarczyk 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 South-Eastern Conf Combinatorics, Graph Theory and Computing, 1975: 15-31.
43 GensG V,LevnerE 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 FrǐmanG A.Foundations of a Structual Theory of Set Addition[M].Providence:American Mathematical Society,1973.
47 TaoT,VuV H.Additive Combinatorics[M].Cambridge:Cambridge University Press,2006.
48 BalogA,SzemerédiE.A statistical theorem of set addition[J].Combinatorica,1994,14(3):263-268.
49 GowersW 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 SudakovB,SzemerédiE,VuV.On a question of erd?s 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 KellererH,MansiniR,PferschyU,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.
Options
Outlines

/

〈 〉