多背包问题近似计算的复杂性

设Π是最大化问题,A是关于Π的近似算法。对Π的每一个实例I,记 R_A(I)=OPT(I)/A(I), 其中OPT(I)是I的最优值,A(I)是算法A求得的近似解的值。记 R_A=inf{4r≥1:对所有的实例I,R_A(I)≤r}, R_A称作A的性能比。如果及_A<+∞,则称A具有常数比。关于Π的多项式时间近似方案     

最小生成树问题在RMESH上的常数时间算法

提出了在n²×mn²的RMESH模型上常数时间的最小生成树算法,并根据PRAM模拟RMESH的结论,得到了在PRAM上O(logn)时间的最小生成树算法。这2个并行算法的时间复杂度都是当前最好的。     

基于XML的网上数学表达式显示技术

提出了一种WEB上数学表达式显示技术的实现方案。该方案克服了以前网上数学表达式多为图形或使用特殊插件的弊端,使用IBM公司的XML4J解析器解析MathML描述的文档,用Java语言实现方案,以Java Applet的形式完成了与常用网页开发工具的集成。     

PRAM模型模拟RMESH模型的2种方案

给出用PRAM模拟RMESH的2种方案：用n个处理器的PRAM-CRCW模型模拟 sqrt(n)×sqrt(n) 个处理器的RMESH模型的时间复杂度为O(nlogn),用n²个处理器的PRAM-CRCW模型模拟 sqrt(n)×sqrt(n) 个处理器的RMESH模型的时间复杂度为O(logn),同时也给出了PRAM-CREW和PRAM-EREW模型模拟的时间复杂度。     

在多项式等价关系下P类的结构

M. R. Carey 和认D. S. Johnson在《计算机和难解性,NP完全性理论导引》一书中说在多项式等价关系下,P类形成一个“最小的”等价类。这个论断是错误的。本文证明在多项式等价关系下,P类可划分成三个等价类:A={Σ~*∶Σ是字母表},B={φ},C=P-(AUB),并且证明在诱导出的偏序关系下,A和B是两个“极小元”。     

关于“图灵归约”形式定义的一点注记

M.R.Garey和D.S.Johnson在[3]中引入“图灵归约”的概念,利用这个概念把NP完全性理论推广到包括组合最优化问题在内的更广的一类问题上。他们用oracle图灵机(OTM)模型给出了图灵归约的形式定义。但是,[3]中给出的这个形式定义是错误的。本文指出了这个错误并给出修正。     

多背包问题的计算

本文讨论二个附加限制的多背包问题:限定总件数的多背包问题和0、1多背包问题,给出了它们的动态规划算法。限定总件数的多背包问题的算法所需的空间为O(BM),时间为O(nBM+kB~2),0、1多背包问题的算法所需的空间为O(min{2~(kn/2),nM~k}),时间为O(min{k·n~(kn/2),knM~k}),其中n为物品的种类数或件数,k为背包数,M=max{M_i:1≤i≤k},M_i(1≤i≤k)是第i个背包允许的最大重量,B是允许装入的最大总件数。