本报告将介绍包括最大独立集问题、SAT问题在内的系列经典NP难问题当前的理论算法结果，并探讨将这些理论工具用于设计实用的实验算法的可行性。

通过预测来改进算法是近年来一个非常活跃的研究课题。我们开始系统地研究带预测信息的机制设计问题。在一系列被广泛研究过的机制设计场景中，我们利用不完美的预测来设计更优的机制，这些机制在两种情况下都有很好的性能：如果预测准确的话，表现会远优于传统机制（一致性），同时即便预测非常不精确也能保持最坏情况下的性能保证（鲁棒性）。

聚类及其相关问题是一类重要的NP难解问题。随着工程应用和各应用领域的发展，在海量数据背景下，人们对各应用领域聚类数据处理也提出了更高的要求。如何优化求解精度和求解效率是聚类算法设计重要核心问题。本报告将介绍如何基于采样、局部搜索等方法，克服离散度依赖、高复杂度等困难，设计k-means，带噪声聚类等问题的近线性（或线性）时间近似算法。

基因组一般地表示为字符序列或字符序列(串)集合。通过序列结构比较分析，确定基因组片段的功能，推断生命的亲缘关系，是生物信息学/计算生物学的基本内容。 介绍寻求两个或多个字符串的最长公共子串或公共子序列的几个组合问题和解答问题的算法进展。重点介绍最长公共样本子序列和最长k元公共子串求解算法。 介绍基因组的重组现象，和寻求字符排列和字符串重组排序的几个组合问题和问题的算法与计算复杂性进展。重点介绍序列的翻转和移位排序问题的求解算法。 浅谈字符串结构相似分析算法设计面临的新挑战，和算法在实际组学数据分析应用中面临的新挑战。

近年来，随着各国政府对个人信息保护的重视，差分隐私技术受到大量关注。对于敏感度有限的问题，现有的研究已经取得了很多成果。然而，对于很多敏感度无限的问题，由于传统的最坏情况最优性无法应用，使得这类问题的算法均缺乏有意义的理论保证。本报告讲阐述如何将实例最优性应用于差分隐私，并介绍一系列这方面的近期成果。

拉丁方补全（LSC）问题旨在为部分填充的拉丁方空格分配符号，使得每一行和每一列中，每个符号恰好出现一次。提出了一种求解LSC问题的快速局部搜索算法。首先提出了一种“禁止行冲突”的搜索空间以及基于交换的邻域结构。其次，采用颜色域松弛技术，允许暂时违反部分约束，以提高高质量解之间的连通性。最后，采用二级目标函数选择邻域动作，同时最小化冲突边数和颜色域违反量。在公共算例集上的实验表明所提出算法的有效性。