我们考察组合优化中的若干基础问题,包括背包问题、子集和问题以及卷积问题。我们希望探索这些问题运行时间最优的算法,即在某些广为接受的复杂性假设下该算法的运行时间应当是(几乎)最优的。最近几年,利用加性组合对经典组合优化问题...我们考察组合优化中的若干基础问题,包括背包问题、子集和问题以及卷积问题。我们希望探索这些问题运行时间最优的算法,即在某些广为接受的复杂性假设下该算法的运行时间应当是(几乎)最优的。最近几年,利用加性组合对经典组合优化问题的算法研究取得了重要的进展,特别地,对背包与子集和问题的若干变种,研究者们得到了运行时间与复杂性下界几乎一致的伪多项式时间算法和多项式时间近似方案。本文将选择其中具有代表性的若干成果展开综述,旨在展示目前已经被研究者们所注意到的加性组合定理与离散优化问题间的联系。特别地,我们将探讨:(ⅰ)有限加和定理及其在背包问题与子集和问题中的应用;(ⅱ) S zemerédi-Vu和集定理及其在子集和问题中的应用;(ⅲ) Balog-Szemerédi-Gowers定理及其在有解单调卷积问题中的应用。展开更多
在线展示广告发展迅猛,按点击付费(cost per click,CPC)的保量合同是在线展示广告的一种重要合同形式。基于实际,在制定广告投放决策时曝光供应量通常是不确定的,其概率分布难以精确获知,仅知部分分布信息。本文利用分布鲁棒优化框架,...在线展示广告发展迅猛,按点击付费(cost per click,CPC)的保量合同是在线展示广告的一种重要合同形式。基于实际,在制定广告投放决策时曝光供应量通常是不确定的,其概率分布难以精确获知,仅知部分分布信息。本文利用分布鲁棒优化框架,构建寻求以已知信息为特征的不确定集,并在最坏情形下寻求最优广告投放策略。建立分布鲁棒机会约束模型并给出求解算法,进行了仿真分析。数值算例结果显示,设计的广告投放优化模型和相应的求解算法具有较好的表现。展开更多
文摘我们考察组合优化中的若干基础问题,包括背包问题、子集和问题以及卷积问题。我们希望探索这些问题运行时间最优的算法,即在某些广为接受的复杂性假设下该算法的运行时间应当是(几乎)最优的。最近几年,利用加性组合对经典组合优化问题的算法研究取得了重要的进展,特别地,对背包与子集和问题的若干变种,研究者们得到了运行时间与复杂性下界几乎一致的伪多项式时间算法和多项式时间近似方案。本文将选择其中具有代表性的若干成果展开综述,旨在展示目前已经被研究者们所注意到的加性组合定理与离散优化问题间的联系。特别地,我们将探讨:(ⅰ)有限加和定理及其在背包问题与子集和问题中的应用;(ⅱ) S zemerédi-Vu和集定理及其在子集和问题中的应用;(ⅲ) Balog-Szemerédi-Gowers定理及其在有解单调卷积问题中的应用。
文摘在线展示广告发展迅猛,按点击付费(cost per click,CPC)的保量合同是在线展示广告的一种重要合同形式。基于实际,在制定广告投放决策时曝光供应量通常是不确定的,其概率分布难以精确获知,仅知部分分布信息。本文利用分布鲁棒优化框架,构建寻求以已知信息为特征的不确定集,并在最坏情形下寻求最优广告投放策略。建立分布鲁棒机会约束模型并给出求解算法,进行了仿真分析。数值算例结果显示,设计的广告投放优化模型和相应的求解算法具有较好的表现。
