摘要 多样性公平k-中位问题在数据摘要等对聚类中心选取方式的公平性要求较高的聚类应用领域发挥重要作用.给定一个用户集合、?个设施集合以及正整数k,该问题的目标是在每个设施集合中开设一个规模受限的子集,使得开设设施数量不超过k,且每个用户与距离最近的开设设施之间具有较高的相似度.本文将多样性公平k-中位问题实例映射为低维空间中的小规模实例,并围绕实例中的点划分空间以估计最优解中开设设施的位置.基于这一思路,本文在d-维欧氏空间中为多样性公平k-中位问题提出了时间复杂度为O（nd log n）+2?k+（kε-1）O（1）nO（1）的（1+ε）-近似算法,其中,n为设施与用户数量之和.该结果改进了此前人们在更一般化的度量空间中利用相近的固定参数时间得到的(1+2e-1+ε)-近似比.

关键词 固定参数算法; 近似算法; k-中位问题; 设施选址; 采样; parameterized algorithm; approximation algorithm; k-median; facility location; sampling

摘要 最大独立集问题是计算机科学中最基础且重要的NP完全问题之一.本文研究了超图上最大独立集问题（MISH）和超图上带惩罚的最大独立集问题（PC-MISH）的精确算法.给定一个超图,MISH问题旨在寻找图中最大的独立集,其中,超图中的独立集是一些两两不包含在同一超边的顶点构成的点子集.而PC-MISH问题是MISH问题的松弛化变体.在PC-MISH问题中,仍然寻找一个点集X,但是它允许违背“独立”的性质,也就是说,允许超边包含X中的多个顶点.这个集合X的价值定义为X的大小减去包含至少两个X中的顶点的超边数量.而PC-MISH问题旨在找到一个价值最大的点集.本文研究MISH和PC-MISH问题以n以及l=n+m为参数的精确算法,其中n是超图中顶点的个数,m是超图中超边的条数.通过利用最大独立集问题在一般无向图上的精确算法可以直接得到MISH问题O*(1.1996^n)时间的算法.此外,本文证明了PC-MISH问题可以在O*(1.9548^n)时间内求解,打破了穷举搜索的2^n时间复杂度.进一步,本文重点给出MISH问题一个O(1.1520^l)时间的算法和PC-MISH问题一个O(1.3982^l)时间的算法,分别改进之前时间为O(1.1550^l)和1.5^l2^{o(l)}的精确算法.

关键词 精确算法; 最大独立集问题; 带惩罚最大独立集问题; 超图; 最小子集反馈集问题; exact algorithms; maximum independent set problem; prize-collecting maximum independent set problem; hypergraphs; minimum subset feedback vertex set problem

摘要 图边删除问题中一类重要问题是研究是否可以删除图中不超过k条边之后使得剩余的图不存在某个子图结构H,而子图H为顶点个数不超过4的连通图的情况被研究得最为广泛.本文主要考虑H为Paw图(三角形其中一个顶点再邻接一条边)的情况,称为Paw图–边删除问题,并为该问题设计了一个32k个顶点的问题核.这是该问题的第1个线性顶点大小的问题核.文中主要的技术是结合两个新的皇冠分解的变体来分析图的结构从而对图进行简化.

关键词 图算法; 核心化算法; H-边删除问题; Paw图-边删除问题; 皇冠分解技术; graph algorithms; kernelization; H-edge covering; Paw-edge covering; crown decomposition

摘要 给定度量空间中的一个设施集合与一个带有最低服务级别要求的用户集合,优先k-设施选址问题的目标是开设最多k个设施,在每个开设设施上安置不同级别的服务,并将每个用户连接到一个能满足其服务级别要求的开设设施上,使得设施开设费用、服务安置费用与用户连接费用之和最小.本文利用拉格朗日(Lagrange)松弛技术求解优先k-设施选址问题,针对用户的服务级别要求提出了新的确定化舍入方法,并基于此给出了多项式时间的(7.9533+ε)-近似算法.这是关于该问题的第一个常数近似算法.

关键词 设施选址; 近似算法; 拉格朗日松弛; facility location; approximation algorithms; Lagrangian relaxation

摘要 LinUCB算法是求解上下文多臂老虎机问题的一种典型算法,被广泛应用于新闻投放、产品推荐、医疗资源分配等场景中.目前对该算法的安全性研究略显薄弱,这就要求研究者进一步加深对该算法的攻击方式的研究,以作出具有针对性乃至泛用性的防御措施.本文提出了两种通过添加虚假数据的方式对LinUCB算法进行离线数据投毒攻击的攻击方案,即TCA方案(target context attack)与OCA方案(optimized context attack).前者是基于训练数据与目标上下文的相似性来生成投毒数据的;后者是建模一个优化问题,通过求解该问题来构造投毒数据,是前者的优化版本.实验测试表明,仅需添加少量投毒数据作为攻击成本即可实现对攻击目标的100%攻击成功率.

关键词 上下文多臂老虎机; LinUCB 算法; 数据投毒攻击; 白盒攻击; 优化问题; contextual multi-armed bandit; LinUCB; data poisoning attack; white-box attack; optimization problem