博士论文研究NP难组合优化问题，利用对偶性，在离线、在线和策略设置下，针对覆盖、匹配和调度问题，寻求更优近似解。
原文标题：【博士论文】在离线、在线和策略设置下通过对偶性进行的近似
原文作者：数据派THU
冷月清谈：
怜星夜思：
2、文章提到了“超越最坏情况分析”，这种分析方法与传统的“最坏情况分析”相比，有哪些优势和局限性？在实际问题中，我们应该如何选择使用哪种分析方法？
3、文章中提到的“对偶拟合（Dual fitting）”框架，如何理解其在近似算法、在线算法和博弈论分析中的统一性？这种统一性对于算法设计和分析有什么意义？
原文内容
来源：专知本文约1000字，建议阅读5分钟本论文研究的核心问题可概括如下：给定一个 NP-难组合优化问题及其一个次优解。
本论文研究的核心问题可概括如下：给定一个 NP-难组合优化问题及其一个次优解（例如通过高效近似算法获得），该次优解与最优解的接近程度如何？解的质量通过最坏情况比率（Worst-case ratio）来衡量，即在所有输入实例中，算法解的成本与最优解成本的比值。
本论文旨在开发新技术，针对三类基础组合优化问题——覆盖问题（Covering）、匹配问题（Matching）和调度问题（Scheduling），为上述问题证明紧确界（Tight bounds）。此外，我们在三个不同但相关的语境下探讨这一问题。首先，次优解可由标准的近似算法获得，该算法可以提前获取全部输入信息，此时关注的比率称为近似比（Approximation ratio）。其次，在更具局限性的计算模型中，输入随时间部分揭示，要求在线算法（Online algorithm）在每一步做出不可撤销的决策，此时对应的衡量指标为竞争比（Competitive ratio）。最后，解可能作为博弈论中的平衡态（例如纳什平衡）出现，在这种情况下，相关的衡量指标被称为无序代价（Price of anarchy）。
本研究所有结果的一个统一主题是利用凸规划松弛（Convex programming relaxations），如线性规划（LP）和半正定规划（SDP）。特别是，我们频繁利用凸规划的**对偶性（Duality）**来构建精心选择的对偶解，用以指导各类分析并辅助算法设计。
首先，我们对经典的**顶点覆盖问题（Vertex cover problem）及其标准 LP 松弛开展了超越最坏情况的分析（Beyond the worst-case analysis）。该问题在二分图上可高效求解，而在一般图上通过对 LP 解进行取整可获得 2-近似算法。我们引入了新参数并设计了一种算法，其达到的界限能够在上述两个极端情况之间进行插值。对于三着色图，我们的结果揭示了 LP 的整数值间隙（Integrality gap）**何时因图结构的影响而减小至 1。
其次，我们研究了经典在线二分匹配问题在超图上的扩展，特别关注在线顶点到达模式下的 3-均匀超图。我们为该问题提出了一个最优的**原始-对偶（Primal-dual）**分数算法，并构造了一个对抗实例以确立匹配的上界。此外，针对在线节点度数有界的情形，我们提供了一个优于贪心策略的随机化整数算法。
随后，我们考虑了以最小化加权完成时间之和为目标的若干调度与拥塞问题。我们在单一半正定规划上引入了一个**对偶拟合（Dual fitting）**框架，该框架能够同时为局部搜索算法的近似比、在线算法的竞争比以及博弈的无序代价提供紧确界的简洁证明。通过这一统一框架，我们的研究简化并统一了该领域的重要既有成果。
最后，我们研究了二叉堆上的在线图搜索问题，该问题与求解整数规划的**分枝定界算法（Branch and bound algorithm）**密切相关。我们提供了一种新的随机化算法，虽然略微增加了空间开销，但提升了该问题的已知最佳运行时间。
