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