运筹学学报(中英文) ›› 2025, Vol. 29 ›› Issue (3): 202-222.doi: 10.15960/j.cnki.issn.1007-6093.2025.03.010

• • 上一篇    

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

陈林*   

  1. 浙江大学计算机科学与技术学院, 浙江杭州 310027
  • 收稿日期:2025-03-03 发布日期:2025-09-09
  • 通讯作者: 陈林 E-mail:chenlin198662@zju.edu.cn
  • 基金资助:
    国家自然科学基金(No.62572428)

Application of additive combinatorics in several classic combinatorial optimization problems

CHEN Lin*   

  1. College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, Zhejiang, China
  • Received:2025-03-03 Published:2025-09-09

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

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

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: (i) the finite addition theorem and its application in the algorithmic design for the knapsack problem and the subset sum problem; (ii) Szemerédi-Vu sumset theorem and its application in the algorithmic design for the subset sum problem; and (iii) 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

中图分类号: