English

运筹学学报 >

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

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

第九届中国运筹学会科学技术奖获奖者专辑

加性组合在若干经典组合优化问题中的应用

  • 陈林
展开
  • 1. 浙江大学计算机科学与技术学院, 浙江杭州 310027
陈林  E-mail: chenlin198662@zju.edu.cn

收稿日期: 2025-03-03

  网络出版日期: 2025-09-09

基金资助

国家自然科学基金(62572428)

版权

运筹学学报编辑部, 2025, 版权所有，未经授权，不得转载。
收起

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

摘要

我们考察组合优化中的若干基础问题, 包括背包问题、子集和问题以及卷积问题。我们希望探索这些问题运行时间最优的算法, 即在某些广为接受的复杂性假设下该算法的运行时间应当是(几乎) 最优的。最近几年, 利用加性组合对经典组合优化问题的算法研究取得了重要的进展, 特别地, 对背包与子集和问题的若干变种, 研究者们得到了运行时间与复杂性下界几乎一致的伪多项式时间算法和多项式时间近似方案。本文将选择其中具有代表性的若干成果展开综述, 旨在展示目前已经被研究者们所注意到的加性组合定理与离散优化问题间的联系。特别地, 我们将探讨: (ⅰ) 有限加和定理及其在背包问题与子集和问题中的应用; (ⅱ) Szemerédi-Vu和集定理及其在子集和问题中的应用; (ⅲ) Balog-Szemerédi-Gowers定理及其在有解单调卷积问题中的应用。

关键词： 伪多项式时间算法; 多项式时间近似方案; 背包; 子集和; 加性组合

本文引用格式

陈林 . 加性组合在若干经典组合优化问题中的应用[J]. 运筹学学报, 2025 , 29(3) : 202 -222 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.03.010

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

参考文献

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
文章导航

/

〈 〉