Operations Research Transactions ›› 2025, Vol. 29 ›› Issue (3): 202-222.doi: 10.15960/j.cnki.issn.1007-6093.2025.03.010

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

• Research Article • Previous Articles     Next Articles

Application of additive combinatorics in several classic combinatorial optimization problems

Lin CHEN1,*()   

  1. 1. College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, Zhejiang, China
  • Received:2025-03-03 Online:2025-09-15 Published:2025-09-09
  • Contact: Lin CHEN E-mail:chenlin198662@zju.edu.cn

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

CLC Number: