算法分析进阶：超越最坏情况分析

算法设计中没有灵丹妙药（no silver bullet）——不存在任何一种足够强大和灵活，能够解决所有计算问题的算法思想。同样，算法分析中也没有灵丹妙药，因为对算法进行分析的最具启发性的方法往往取决于问题和应用的细节。然而，典型的算法课程几乎完全停留在一种单一的分析框架上，即最坏情况分析。本书的目的就是纠正这种不平衡。

本书源于斯坦福大学的研究生课程，由40位学者联袂撰写，旨在推广zui坏情况分析的替代方法，以及这些方法的应用，包括聚类、线性规划和神经网络训练等。

译者序<br />前言<br />作者名单第1章  引言1  1.1  算法的最坏情况分析1<br />    1.1.1  不可比较算法的比较1<br />    1.1.2  最坏情况分析带来的好处2<br />    1.1.3  算法分析的目标2<br />  1.2  著名的失败事件和对替代方法的<br />迫切需要3<br />    1.2.1  线性规划的单纯形法3<br />    1.2.2  聚类与NP困难最优化<br />问题3<br />    1.2.3  机器学习的不合理的<br />有效性4<br />    1.2.4  在线算法分析5<br />    1.2.5  最坏情况分析的骗局5<br />  1.3  示例：在线分页问题中的参数<br />化界6<br />    1.3.1  根据引用局部性的参数化6<br />    1.3.2  定理1.1的证明7<br />    1.3.3  讨论8<br />  1.4  本书概述9<br />    1.4.1  最坏情况分析的改进9<br />    1.4.2  确定性数据模型10<br />    1.4.3  半随机模型11<br />    1.4.4  平滑分析12<br />    1.4.5  机器学习和统计学中的<br />应用13<br />    1.4.6  进一步的应用14<br />  1.5  本章注解16<br />  致谢16<br />  参考文献16<br />  练习题17第一部分  最坏情况分析的改进第2章  参数化算法20  2.1  引言20<br />    2.1.1  热身：顶点覆盖问题20<br />  2.2  随机化23<br />    2.2.1  随机分离：集合拆分问题25<br />    2.2.2  去随机化26<br />  2.3  结构上的参数化26<br />  2.4  核心化27<br />    2.4.1  热身：Buss规则27<br />    2.4.2  形式定义以及与FPT的成员<br />关系28<br />    2.4.3  Buss规则在矩阵秩上的<br />推广29<br />  2.5  困难性和最优性30<br />    2.5.1  W\[1\]困难性30<br />    2.5.2  ETH和SETH31<br />    2.5.3  核心化的困难性和最优性32<br />  2.6  展望：新的范例和应用领域33<br />    2.6.1  FPT-近似和有损核心33<br />    2.6.2  P问题中的FPT35<br />    2.6.3  应用领域36<br />  2.7  总体方向36<br />  2.8  本章注解36<br />  参考文献37<br />  练习题40第3章  从自适应分析到实例<br />最优性41  3.1  案例研究1：最大点集合问题41<br />    3.1.1  Jarvis步进算法41<br />    3.1.2  Graham扫描算法42<br />    3.1.3  Marriage Before Conquest<br />算法42<br />    3.1.4  垂直熵43<br />    3.1.5  （忽视顺序的）实例<br />最优性44<br />    3.1.6  部分有序的输入46<br />    3.1.7  不可能性的结果46<br />  3.2  案例研究2：实例最优的聚合<br />算法47<br />    3.2.1  实例最优性47<br />    3.2.2  问题的设定48<br />    3.2.3  阈值算法48<br />    3.2.4  阈值算法的实例最优性49<br />    3.2.5  最优性比上的匹配下界49<br />  3.3  对更多结果和技术的综述50<br />    3.3.1  输入顺序50<br />    3.3.2  输入结构50<br />    3.3.3  顺序与结构之间的协同<br />作用51<br />  3.4  讨论51<br />    3.4.1  与参数化算法的比较51<br />    3.4.2  与在线算法的竞争分析的<br />比较52<br />  3.5  开放式问题精选52<br />    3.5.1  高维的情况52<br />    3.5.2  最大点集合的分层52<br />  3.6  关键要点53<br />  3.7  本章注解53<br />  致谢53<br />  参考文献53<br />  练习题54第4章  资源增广57  4.1  再论在线分页问题57<br />    4.1.1  模型57<br />    4.1.2  FIF和LRU57<br />    4.1.3  竞争比58<br />    4.1.4  资源增广界58<br />  4.2  讨论59<br />  4.3  自私路由问题61<br />    4.3.1  模型和一个推动研究的<br />示例61<br />    4.3.2  资源增广保证62<br />    4.3.3  定理4.4的证明<br />（平行边）62<br />    4.3.4  定理4.4的证明<br />（一般网络）63<br />  4.4  调度问题中速度的改变64<br />    4.4.1  非预知未来调度64<br />    4.4.2  关于SETF的资源增广<br />保证65<br />    4.4.3  引理4.8的证明：准备<br />工作66<br />    4.4.4  引理4.8的证明：主要<br />论证67<br />  4.5  松弛竞争算法69<br />  4.6  本章注解71<br />  致谢71<br />  参考文献71<br />  练习题72第二部分  确定性数据模型第5章  扰动弹性76  5.1  引言76<br />  5.2  组合最优化问题78<br />  5.3  认证算法的设计80<br />  5.4  认证算法示例84<br />  5.5  扰动弹性的聚类问题85<br />    5.5.1  度量扰动弹性蕴含了<br />中心紧邻性87<br />  5.6  2-扰动弹性实例的算法88<br />  5.7  k-median的（3+ε)-认证的<br />局部搜索算法90<br />  5.8  本章注解91<br />  参考文献92<br />  练习题94第6章  近似解稳定性与代理<br />目标95  6.1  引言和动机95<br />  6.2  定义和讨论96<br />  6.3  k-median问题99<br />    6.3.1  定义99<br />    6.3.2  一些令人关注的结果99<br />    6.3.3  算法和证明100<br />    6.3.4  小簇的处理104<br />  6.4  k-means、min-sum以及其他聚类<br />目标105<br />  6.5  聚类应用105<br />  6.6  纳什均衡106<br />  6.7  总体方向107<br />  6.8  开放式问题108<br />  6.9  松弛108<br />  6.10  本章注解108<br />  参考文献109<br />  练习题110第7章  稀疏恢复111  7.1  引言111<br />  7.2  一种简单的只插入流算法112<br />  7.3  删除的处理：线性概略算法113<br />    7.3.1  CountMinSketch：1保证114<br />    7.3.2  CountSketch：2保证116<br />    7.3.3  关于恢复保证的讨论116<br />  7.4  均匀算法118<br />    7.4.1  受限的等距特性118<br />    7.4.2  测量后噪声和测量前<br />噪声119<br />    7.4.3  迭代法120<br />    7.4.4  L1最小化121<br />  7.5  下界122<br />  7.6  不同的测量模型123<br />    7.6.1  一种混合结果：RIP-1矩阵<br />和稀疏矩阵123<br />    7.6.2  傅里叶测量124<br />  7.7  矩阵恢复125<br />  7.8  本章注解127<br />  参考文献127<br />  练习题129第三部分  半随机模型第8章  分布分析132  8.1  引言132<br />    8.1.1  分布分析的利弊132<br />    8.1.2  最优停止问题133<br />    8.1.3  讨论133<br />    8.1.4  阈值规则和先知不等式134<br />  8.2  经典算法的平均情况论证135<br />    8.2.1  快速排序135<br />    8.2.2  线性探测136<br />    8.2.3  装箱问题137<br />  8.3  欧几里得问题的表现良好的平均<br />算法138<br />    8.3.1  2D凸包问题138<br />    8.3.2  平面上的旅行商问题139<br />    8.3.3  讨论141<br />  8.4  随机图和植入模型142<br />    8.4.1  Erds-Rényi随机图142<br />    8.4.2  植入图模型143<br />    8.4.3  讨论144<br />  8.5  健壮的分布分析145<br />    8.5.1  同时具备的接近-最优性145<br />    8.5.2  学习一个接近-最优解145<br />  8.6  本章注解146<br />  致谢146<br />  参考文献147<br />  练习题148第9章  半随机模型简介150  9.1  引言150<br />    9.1.1  半随机模型的示例150<br />  9.2  为什么要研究半随机模型152<br />    9.2.1  平均情况分析153<br />    9.2.2  被噪声污染的信号的<br />恢复154<br />    9.2.3  一个用于最坏情况实例的<br />模型154<br />    9.2.4  NP困难性155<br />  9.3  一些代表性工作155<br />    9.3.1  半随机模型的一些初步<br />结果155<br />    9.3.2  具有单调对抗的植入团/<br />最大独立集156<br />    9.3.3  反驳启发式算法159<br />    9.3.4  关于局部最优解的单调<br />对抗161<br />    9.3.5  可分离半随机模型163<br />    9.3.6  唯一博弈的可分离模型164<br />    9.3.7  宿主型着色框架164<br />  9.4  开放式问题166<br />  致谢167<br />  参考文献167第10章  半随机的随机块模型169  10.1  引言169<br />  10.2  借助半定规划的恢复171<br />    10.2.1  最优性证书171<br />    10.2.2  随机矩阵理论172<br />  10.3  单调对抗下的健壮性173<br />  10.4  精确恢复的信息理论极限174<br />    10.4.1  植入对分174<br />    10.4.2  一般随机块模型175<br />  10.5  部分恢复和置信传播176<br />    10.5.1  置信传播176<br />  10.6  随机与半随机分离的对比178<br />    10.6.1  半随机模型中的信息理论<br />极限178<br />    10.6.2  广播树模型178<br />  10.7  平均情况分析之上180<br />    10.7.1  矩阵补全180<br />    10.7.2  交替最小化181<br />    10.7.3  半随机的矩阵补全182<br />  10.8  半随机混合模型183<br />  参考文献183<br />  练习题185第11章  随机顺序模型186  11.1  动机：选取一个大的元素186<br />    11.1.1  模型和讨论187<br />    11.1.2  路线图188<br />  11.2  秘书问题188<br />  11.3  多秘书问题和其他最大化<br />问题189<br />    11.3.1  忽视顺序算法189<br />    11.3.2  自适应顺序算法193<br />  11.4  最小化问题196<br />    11.4.1  在线匹配中的增量的<br />最小化197<br />    11.4.2  装箱问题198<br />    11.4.3  设施选址199<br />  11.5  相关模型和扩展199<br />    11.5.1  加入更多随机性200<br />    11.5.2  减少随机性201<br />    11.5.3  随机顺序算法到其他模型的<br />扩展202<br />  11.6  本章注解203<br />  致谢204<br />  参考文献204<br />  练习题206第12章  自我改进算法207  12.1  引言207<br />    12.1.1  排序问题208<br />  12.2  信息论基础210<br />  12.3  自我改进排序算法212<br />    12.3.1  限制阶段213<br />    12.3.2  训练阶段214<br />    12.3.3  自我改进排序算法的<br />下界216<br />  12.4  2D最大点问题的自我改进<br />算法217<br />    12.4.1  证书和线性决策树218<br />    12.4.2  相关的自我改进算法219<br />  12.5  更多的自我改进算法221<br />  12.6  关于自我改进模型的评判222<br />  致谢223<br />  参考文献223<br />  练习题224第四部分  平滑分析第13章  局部搜索的平滑分析228  13.1  引言228<br />  13.2  运行时间的平滑分析229<br />    13.2.1  主要思想229<br />    13.2.2  2-opt的简单界229<br />    13.2.3  界的改进的可能性232<br />    13.2.4  k-means方法的界234<br />  13.3  近似比的平滑分析240<br />    13.3.1  2-opt近似比的简单界241<br />    13.3.2  改进的2-opt的平滑<br />近似比241<br />  13.4  讨论和开放式问题242<br />    13.4.1  运行时间242<br />    13.4.2  近似比243<br />  13.5  本章注解243<br />  参考文献244<br />  练习题245第14章  单纯形法的平滑分析247  14.1  引言247<br />  14.2  影子顶点单纯形法247<br />  14.3  连续最短路径算法251<br />    14.3.1  SSP的平滑分析253<br />  14.4  具有高斯约束的线性规划255<br />    14.4.1  二维中的影子界258<br />    14.4.2  更高维度中的影子界260<br />  14.5  讨论263<br />  14.6  本章注解264<br />  参考文献265<br />  练习题266第15章  多目标最优化中帕累托<br />曲线的平滑分析267  15.1  计算帕累托曲线的算法267<br />    15.1.1  背包问题267<br />    15.1.2  最短路径问题270<br />    15.1.3  多目标和其他最优化<br />问题272<br />    15.1.4  近似帕累托曲线273<br />  15.2  帕累托最优解的数量273<br />    15.2.1  背包问题274<br />    15.2.2  一般模型278<br />    15.2.3  多目标最优化问题280<br />  15.3  二元最优化问题的平滑<br />复杂性280<br />  15.4  结论282<br />  15.5  本章注解282<br />  参考文献283<br />  练习题284第五部分  机器学习和统计学中的应用第16章  分类噪声286  16.1  引言286<br />  16.2  模型287<br />  16.3  最佳情况和最坏情况287<br />    16.3.1  样本复杂性287<br />    16.3.2  计算复杂性288<br />  16.4  在边缘分布上的假定所带来的<br />好处290<br />    16.4.1  借助多项式回归的计算<br />上的改进290<br />    16.4.2  借助局部化的计算上的<br />改进293<br />  16.5  在噪声上的假定所带来的<br />好处297<br />    16.5.1  对更为良性的噪声模型在<br />统计上的改进297<br />    16.5.2  对更为良性的噪声模型在<br />计算上的改进298<br />  16.6  结束语和当前研究方向301<br />  参考文献302<br />  练习题303第17章  健壮的高维统计304  17.1  引言304<br />  17.2  健壮的均值估计306<br />    17.2.1  主要困难和高层次的<br />直觉306<br />    17.2.2  良好集和稳定性307<br />    17.2.3  未知凸规划方法310<br />    17.2.4  过滤方法311<br />  17.3  超越健壮均值估计315<br />    17.3.1  健壮的随机最优化315<br />    17.3.2  健壮的协方差估计316<br />    17.3.3  可解码列表的学习316<br />    17.3.4  健壮的稀疏估计317<br />    17.3.5  高阶矩的健壮估计317<br />  17.4  本章注解317<br />  参考文献318<br />  练习题319第18章  最近邻分类与搜索321  18.1  引言321<br />  18.2  最近邻搜索的算法问题321<br />    18.2.1  近似的最近邻搜索的<br />哈希法322<br />    18.2.2  精确的最近邻搜索的<br />树结构323<br />    18.2.3  内蕴维数的概念324<br />    18.2.4  对最近邻搜索中的内蕴<br />维数的自适应性325<br />    18.2.5  一种具有特定于实例的<br />界的随机化树结构326<br />    18.2.6  小结：最近邻搜索算法的<br />分析327<br />  18.3  k-最近邻分类的统计复杂性328<br />    18.3.1  统计学习框架328<br />    18.3.2  极小极大最优性329<br />    18.3.3  自适应速度与最坏情况速度<br />的对比329<br />    18.3.4  低噪声条件和快收敛<br />速度332<br />    18.3.5  小结：统计复杂性334<br />  18.4  本章注解334<br />  参考文献335<br />  练习题336第19章  高效的张量分解338  19.1  张量导引338<br />    19.1.1  低秩分解和秩338<br />  19.2  在学习隐变量模型上的应用340<br />    19.2.1  借助张量分解的矩量法：<br />一种通用的“秘方”340<br />    19.2.2  案例研究341<br />  19.3  满秩设定下的高效算法343<br />    19.3.1  同时诊断算法<br />（Jennrich算法）343<br />    19.3.2  在学习应用中的意义345<br />  19.4  平滑分析和过完备设定345<br />    19.4.1  平滑分析模型345<br />    19.4.2  使Jennrich算法适用于<br />过完备设定346<br />    19.4.3  引理19.13的概略证明348<br />    19.4.4  在应用中的意义350<br />  19.5  用于张量分解的其他算法350<br />  19.6  讨论和一些开放式问题351<br />  致谢352<br />  参考文献352<br />  练习题354第20章  主题模型与非负矩阵因式<br />分解355  20.1  引言355<br />  20.2  非负矩阵因式分解357<br />    20.2.1  非负矩阵因式分解的<br />困难性357<br />    20.2.2  非负矩阵因式分解的<br />唯一性358<br />    20.2.3  可分性的几何解释359<br />    20.2.4  关于可分的NMF的<br />算法359<br />    20.2.5  进一步的应用和讨论361<br />  20.3  主题模型361<br />    20.3.1  张量分解362<br />    20.3.2  纯主题模型的应用362<br />    20.3.3  扩展到混合模型363<br />    20.3.4  锚定词算法365<br />    20.3.5  进一步的讨论367<br />  20.4  结语：词嵌入以及进一步的<br />讨论367<br />  参考文献368<br />  练习题370第21章  为什么局部方法能够求解<br />非凸问题371  21.1  引言371<br />  21.2  分析技术：landscape的特征<br />描述371<br />    21.2.1  收敛到局部最小值371<br />    21.2.2  局部最优性与全局<br />最优性372<br />    21.2.3  流形约束最优化的<br />landscape373<br />  21.3  广义线性模型373<br />    21.3.1  群体风险分析374<br />    21.3.2  经验风险的集中性375<br />  21.4  矩阵因式分解问题375<br />    21.4.1  主成分分析375<br />    21.4.2  矩阵补全377<br />  21.5  张量分解的landscape379<br />    21.5.1  正交张量分解的非凸最优化<br />和全局最优性379<br />    21.5.2  所有局部最优解都是<br />全局最优解380<br />  21.6  综述与展望：神经网络的<br />最优化381<br />  21.7  本章注解384<br />  参考文献384第22章  过参数化模型中的泛化387  22.1  背景和动机387<br />    22.1.1  经验风险与泛化差距388<br />  22.2  推导泛化的工具389<br />    22.2.1  算法稳定性389<br />    22.2.2  均匀稳定性389<br />    22.2.3  经验风险最小化的<br />稳定性390<br />    22.2.4  正则化391<br />    22.2.5  均匀收敛391<br />    22.2.6  Rademacher复杂度392<br />  22.3  过参数化：经验现象393<br />    22.3.1  模型复杂度的影响393<br />    22.3.2  最优化与泛化的对比394<br />    22.3.3  被弱化的显式正则化的<br />作用395<br />  22.4  过参数化模型的泛化界395<br />    22.4.1  集成方法的margin值<br />的界395<br />    22.4.2  线性模型的margin值<br />的界396<br />    22.4.3  神经网络的margin值<br />的界396<br />    22.4.4  隐式正则化397<br />    22.4.5  插补的界398<br />  22.5  实证检验和留出估计398<br />    22.5.1  留出法398<br />    22.5.2  机器学习的基准399<br />  22.6  展望未来400<br />  22.7  本章注解400<br />  致谢401<br />  参考文献401<br />  练习题402第23章  实例最优的分布检验与<br />学习403  23.1  检验和学习离散分布403<br />  23.2  实例最优的分布学习404<br />    23.2.1  理解Opt基准406<br />    23.2.2  Good-Turing频率估计与<br />定理23.3的证明406<br />    23.2.3  估计未看到的元素：在忽略<br />置换的意义上重建分布408<br />  23.3  一致性检验410<br />    23.3.1  概述411<br />    23.3.2  样本复杂度f(p,）的<br />解释411<br />    23.3.3  实例最优算法412<br />  23.4  题外话：一种自动化不等式证明<br />算法413<br />    23.4.1  不等式的非数学证明：<br />peg游戏414<br />  23.5  其他检验问题的超越最坏情况<br />分析416<br />  23.6  本章注解416<br />  参考文献417<br />  练习题417第六部分  进一步的应用第24章  超越竞争分析420  24.1  引言420<br />  24.2  访问图模型421<br />  24.3  扩散对抗模型424<br />    24.3.1  讨论425<br />  24.4  随机模型426<br />    24.4.1  马尔可夫模型426<br />    24.4.2  两全其美吗428<br />  24.5  在线算法的直接比较429<br />    24.5.1  比较分析429<br />  24.6  我们该何去何从430<br />  24.7  本章注解430<br />  参考文献431<br />  练习题434第25章  论SAT求解器的不合理<br />的有效性435  25.1  引言：布尔SAT问题及其<br />求解器435<br />    25.1.1  核心问题436<br />  25.2  冲突驱动子句学习的SAT<br />求解器437<br />  25.3  SAT求解器的证明复杂性441<br />    25.3.1  CDCL和归结之间的<br />等价性441<br />    25.3.2  Res和CDCL SAT求解器的<br />下界和上界443<br />  25.4  证明搜索、可自动化性以及<br />CDCL SAT求解器443<br />  25.5  布尔公式的参数认识444<br />  25.6  证明复杂性、机器学习和<br />求解器设计447<br />  25.7  结论和未来的方向448<br />  参考文献448第26章  简单哈希函数何时可以<br />满足需求451  26.1  引言451<br />    26.1.1  模型452<br />    26.1.2  结果452<br />    26.1.3  应用453<br />    26.1.4  前景453<br />  26.2  准备工作454<br />    26.2.1  符号454<br />    26.2.2  哈希法454<br />    26.2.3  块源455<br />    26.2.4  随机性提取器455<br />  26.3  块源的哈希457<br />  26.4  应用：链式哈希法458<br />  26.5  块源提取的最优化459<br />  26.6  应用：线性探测法460<br />  26.7  其他应用461<br />  26.8  本章注解462<br />  致谢463<br />  参考文献463<br />  练习题465第27章  先验独立拍卖466  27.1  引言466<br />  27.2  收益最大化拍卖“速成<br />课程”467<br />    27.2.1  福利最大化：次高价格<br />拍卖和VCG拍卖467<br />    27.2.2  最坏情况下的收益<br />最大化468<br />    27.2.3  平均情况下的收益最大化<br />和Myerson理论468<br />  27.3  先验独立性的定义470<br />    27.3.1  关于定义的讨论470<br />  27.4  基于样本的方法：单一物品<br />问题472<br />    27.4.1  如何获取样本472<br />    27.4.2  单一竞拍者，单一样本473<br />    27.4.3  多竞拍者，单一样本474<br />    27.4.4  多样本：样本复杂性475<br />    27.4.5  下界和胎紧性476<br />  27.5  基于竞争的方法：多物品<br />问题476<br />    27.5.1  竞争复杂性477<br />    27.5.2  单位需求的竞拍者478<br />    27.5.3  下界和胎紧性479<br />    27.5.4  可叠加的竞拍者479<br />  27.6  总结480<br />  27.7  本章注解480<br />  致谢481<br />  参考文献481<br />  练习题482第28章  社交网络的无分布<br />模型483  28.1  引言483<br />    28.1.1  社交网络具有特殊的<br />结构483<br />  28.2  c-闭合图的团484<br />    28.2.1  三元闭包484<br />    28.2.2  c-闭合图484<br />    28.2.3  计算最大团：一种回溯<br />算法485<br />    28.2.4  计算最大团：固定参数的<br />易处理性486<br />    28.2.5  定理28.5的证明487<br />  28.3  三角形稠密图的结构488<br />    28.3.1  三角形稠密图488<br />    28.3.2  三角形稠密图的可视化488<br />    28.3.3  逆定理489<br />    28.3.4  定理28.9的概略证明489<br />  28.4  幂律有界网络490<br />    28.4.1  幂律度分布及其性质490<br />    28.4.2  PLB图491<br />    28.4.3  三角形的计数492<br />    28.4.4  讨论493<br />  28.5  BCT模型493<br />  28.6  讨论495<br />  28.7  本章注解496<br />  致谢497<br />  参考文献497<br />  练习题497第29章  数据驱动的算法设计499  29.1  动机和背景499<br />  29.2  借助统计学习的数据驱动的<br />算法设计500<br />    29.2.1  子集选择问题的贪心<br />算法502<br />    29.2.2  聚类问题504<br />    29.2.3  其他应用和一般结果507<br />  29.3  借助在线学习的数据驱动的<br />算法设计509<br />  29.4  总结和讨论513<br />  参考文献513第30章  带预测的算法515  30.1  引言515<br />    30.1.1  预热：二叉搜索515<br />    30.1.2  在线算法：滑雪板租赁516<br />    30.1.3  模型517<br />  30.2  sketch的计数517<br />  30.3  学习型Bloom过滤器518<br />  30.4  带预测的缓存问题520<br />    30.4.1  要预测什么520<br />    30.4.2  标记算法521<br />    30.4.3  缓存问题小结522<br />  30.5  带预测的调度523<br />    30.5.1  带预测的简单模型523<br />    30.5.2  更一般的作业服务时间524<br />    30.5.3  调度队列525<br />  30.6  本章注解527<br />  参考文献527<br />  练习题528ⅩⅦ