反馈集问题的研究进展

反馈集问题（feedback set problem）是计算机科学中研究最为广泛和深入的图上NP完全问题之一,其在并发计算、大规模集成电路、编码设计、软件验证、社交网络分析等领域均存在重要的应用. 子集反馈集问题（subset feedback set problem）是反馈集问题的一种更一般化的形式,更加具有普适性和实用性. 近年来,这2个问题在计算复杂性上的分类工作已逐步完善,在算法领域也已出现许多重要的突破. 相关研究工作分为2个部分进行介绍. 第1部分详尽地介绍了反馈集和子集反馈集各种不同版本的问题,梳理了它们之间的一些重要关系,并介绍了这些问题在一般图上的计算复杂性. 第2部分系统性地介绍了反馈集和子集反馈集问题在一些重要子图类上的计算复杂性,包括度有界的图类、平面图类、竞赛图图类、相交图类、禁止图图类和二部图图类. 最后对反馈集和子集反馈集问题的研究现状进行分析和总结,概括了目前主流的研究趋势.

     

The hardness of approximation: Gap location

We refine the complexity analysis of approximation problems by relating it to a new parameter calledgap location. Many of the results obtained so far for approximations yield satisfactory analysis with respect to this refined parameter, but some known results (e.g.,max-k-colorability, max 3-dimensional matching andmax not-all-equal 3sat) fall short of doing so. As a second contribution, our work fills the gap in these cases by presenting new reductions.Next, we present definitions and hardness results of new approximation versions of some NP-complete optimization problems. The problems we treat arevertex cover (for which we define a different optimization problem from the one treated in Papadimitriou & Yannakakis 1991),k-edge coloring, andset splitting.     

Pricing Loss Leaders Can be Hard

Consider the problem of pricing n items under an unlimited supply with m single minded buyers,each of which is interested in at most k of the items.The goal is to price each item with profit margin p1,p2,...,pn so as to maximize the overall profit.There is an O(k)-approximation algorithm by Balcan and Blum when the price on each item must be above its margin cost;i.e.,each pi > 0.We investigate the above problem when the seller is allowed to price some of the items below their margin cost.It was shown by Balcan et al.that by pricing some of the items below cost,the seller could possibly increase the maximum profit by Ω(log n) times.These items sold at low prices to stimulate other profitable sales are usually called loss leader.It is unclear what kind of approximation guarantees are achievable when some of the items can be priced below cost.Understanding this question is posed as an open problem by Balcan and Blum.In this paper,we give a strong negative result for the problem of pricing loss leaders .We prove that assuming the Unique Games Conjecture (UGC),there is no constant approximation algorithm for item pricing with prices below cost allowed even when each customer is interested in at most three items.Conceptually,our result indicates that although it is possible to make more money by selling some items below their margin cost,it can be computationally intractable to do so.     

基于继承图的面向对象软件复杂性度量研究

面向对象软件开发是一种新的可以减少成本、提高可用性和灵活性的高效的软件系统开发方法。复杂性度量在软件开发中起着非常重要的作用,它可减少整个开发周期的费用,但目前还没有成熟的用于面向对象软件复杂性的度量方法。文章首先通过继承图描述面向对象软件复杂性度量方法,然后讨论了单元重复继承算法,最后给出了具体实例。     

多变量预测控制结构分解的图论方法

预测控制算法的计算复杂度主要由变量个数和控制时域决定,而大型复杂系统中变量个数较多将导致计算量大的问题,尤其在有约束预测控制的优化求解中增加较重的计算负担.本文针对此问题利用邻接矩阵、可达矩阵和关联矩阵梳理系统传递函数模型中变量之间的关联,将有关联的控制变量划分为一个子系统,进而将一个大系统分解成若干独立子系统,即可将一个高维度的优化求解问题分解成多个维度较低的子优化问题,降低计算复杂度以达到减少计算量的目的.最后将其应用在多变量有约束的双层结构预测控制算法中,通过仿真进行验证.     

Time Complexity of Evolutionary Algorithms for Combinatorial Optimization： A Decade of Results

Computational time complexity analyzes of evolutionary algorithms (EAs) have been performed since the mid-nineties. The first results were related to very simple algorithms,such as the (1 1)-EA,on toy problems.These efforts produced a deeper understanding of how EAs perform on different kinds of fitness landscapes and general mathematical tools that may be extended to the analysis of more complicated EAs on more realistic problems.In fact,in recent years,it has been possible to analyze the (1 1)-EA on combinatorial optimization problems with practical applications and more realistic population-baeed EAs on structured toy problems. This paper presents a survey of the results obtained in the last decade along these two research lines.The most common mathematical techniques are introduced,the basic ideas behind them are discussed and their elective applications are highlighted.Solved problems that were still open are enumerated as are those still awaiting for a solution.New questions and problems arisen in the meantime are also considered.     

欧氏空间货郎担问题的一个多项式时间近似方案的改进与实现

货郎担问题的实例是给定n个结点和任意一对结点{i,j}之间的距离di,j,要求找出一条封闭的回路,该回路经过每个结点一次且仅一次,并且费用最小,这里的费用是指回路上相邻结点间的距离和.货郎担问题是NP难的组合优化问题,是计算机算法研究的热点之一.在过去几十年中,这一经典问题成为许多重要算法思想的测试平台,并促使一些研究领域的出现,如多面体理论和复杂性理论.欧氏空间上的货郎担问题,结点限制在欧氏空间,距离定义为欧氏距离.即使是这样,欧氏空间上的货郎担问题仍然是NP难的.1996年,Arora提出欧氏空间上货郎担问题的第1个多项式时间近似方案.对其中货郎担问题的算法进行了改进：提出一种新的构造方法,使应用于该算法的“补丁引理”结论由常数6改进到常数3,从而使算法的时间复杂度大幅减少;同时,编程实现了该算法,并对实验结果进行了分析.     

An O(N) algorithm for polygonal approximation

A new, sequential algorithm for polygonal approximation of plane, closed curves is presented. It runs in O(N) time and is based on a tolerance independent of the scale factor.     

工厂地址集中的k-种产品选址问题的近似算法

k-种产品工厂选址问题是：给定一个客户集合和一个可以建立工厂的地址集合,每个客户需要k-种产品,一个工厂只能为客户提供一种产品。考虑的工厂假设相对集中,即假设任何工厂之间的距离都不大于工厂与客户之间的距离。对于没有建厂费用的问题,当k=2时证明了它是一个NP完全问题,对任意的k给出了一个最坏性能比不大于2-1/k的近似算法。对于有建厂费用的问题,给出了一个最坏性能比不大于2的近似算法。