【摘 要】
：
In this paper, the approximation forfour kinds of knapsack problemswith multiple constraints is studied:0/1 Multiple Constraint Knapsack Problem (0/1MCKP), Inte
【机 构】
：
Department of Computer Science and Technology
【基金项目】
：
Science Foundation ofPeking University;国家科技攻关项目
论文部分内容阅读
In this paper, the approximation forfour kinds of knapsack problemswith multiple constraints is studied:0/1 Multiple Constraint Knapsack Problem (0/1MCKP), Integer MultipleConstraint Knapsack Problem (Integer MCKP), 0/1 k-ConstraintKnapsackProblem (0/1 k-CKP) and Integer k-Constraint Knapsack Problem(Integerk-CKP). The following results are obtained:1) Unless NP = co-R, no polynomial time algorithm approximates 0/1MCKP orInteger MCKP within a factor k(1/2)-σ for anyσ>0;unless NP=P, no polynomial timealgorithm approximates 0/1 MCKP orInteger MCKP within a factor k(1/4)-σ for any σ>0, where kstands for the number of constraints.2) For any fixed positive integer k, 0/1 k-CKP has a fullypolynomial timeapproximation scheme (FPTAS).3) For any fixed positive integer k, Integer k-CKP has a fast FPTASwhich hastime complexity and space complexity O(n+(1/ε3)),and finds anapproximate solution to within of the optimal solution.
其他文献
Objective: To investigate the apoptotic threshold of adriamycin (ADM) and cisplatin (CDDP) on hepatocellular carcinoma (HCC). Methods: Sensitivities of ADM and
“关系”一词具有鲜明的中国特色,在中国文化中占有一个相当重要的地位,因此有不少学者建议将其音译为guanxi以避免其文化内涵损失。本文对“关系”一词的英译进行再一番探讨
Some characteristics of the rice (Oryza sativa L.) root were found in the experiment of unilaterally irradiating the roots which were planted in water: (ⅰ) All
The binuclear complex [Sm2(C12H8N2)2(C6H5COO)6] has been prepared and structurally analyzed by single crystal X-ray diffraction. The complex crystallizes in the
本文从开展探究式学习的背景、意义人手,较为全面系统介绍大学英语课堂开展探究式学习的教学方式、操作过程.本文还展示了一些具体的课例.并针对实际课堂提出了一些建议.
目的 建立高效液相色谱法测定女贞子中特女贞苷的含量的方法.方法 采用Alhima C18色谱柱(4.6mm×250mm,5 μm),乙腈-水为流动相,流速1.0 ml/min,检测波长230 nm,柱温25℃.在
The title compound (C31H33NO6, Mr =515.58) was synthesized by the reaction of N-diphenylmethylidene aniline and ethyl diazoacetate. Its crystal belongs to the o
目的:探讨102例感冒早期简易治疗的疗效.方法:临床统计了102例感冒早期患者,行口服克感敏治疗,同时行白糖开水口服.观察患者的临床病症改善情况,统计分析其实际临床疗效.结果
The studies of NO chemisorption on TiO2(110) surface are the base of research to NO decomposed to N2O on TiO2 surface. In this paper, 12 kinds of possible model
A so-called ISF method for predicting geomagnetic disturbances caused by solar wind storm blowing to the earth is suggested. The method is based on a combined a