2. 您的位置
3. 首页
4. 期刊论文
5. An Optimal Parallel Algorithm for the Knapsack Problem Based on EREW

An Optimal Parallel Algorithm for the Knapsack Problem Based on EREW

来源 :西南交通大学学报：英文版 | 被引量 : 0次 | 上传用户：cupcome

【摘 要】

：

A new parallel algorithm is proposed for the knapsack problem where the method of divide and conquer is adopted. Based on an EREW-SIMD machine with shared memor

【作 者】

：

李肯立 蒋盛益 王卉 李庆华 

【机 构】

：

SchoolofComputerScienceandTechnology

【出 处】

：

西南交通大学学报：英文版

【发表日期】

：

2003年2期

【关键词】

：

平行运算 背包问题 EREW-SIMD模型 内存冲突 算法理论 knapsack problem  NP-complete  parallel algorith 

【基金项目】

：

国家自然科学基金，国家高技术研究发展计划(863计划)

下载到本地 , 更方便阅读

下载此文 赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

A new parallel algorithm is proposed for the knapsack problem where the method of divide and conquer is adopted. Based on an EREW-SIMD machine with shared memory, the proposed algorithm utilizes O(2n/4)1-ε processors, 0≤ε≤1, and O(2n/2) memory to find a s

其他文献

Distributed Broker-Agent Architecture for Multimedia Communications Traversing NAT／Firewall in NGN

The forthcoming Next Generation Network (NGN) is an all IP network. Multimedia communications over IP networks are a type of bundled session communications, whi

期刊

下一代网络多媒体通信穿越NAT/防火墙代理Broker-agent Next Generation Network Multimedia commu

高级技能人才的培养目标和KSA──Q模式

高级技能人才的培养目标和ＫＳＡ──Ｑ模式在积极发展高等职业教育的今天，高级技工学校能否生存和发展，除了要进行教学规律的探索和教学过程的改革外．还取决于培养目标是否符合国家经济

期刊

高级技能人才培养目标能力培养高等职业教育高级技工学校职业岗位Q模式技能训练操作技能一般能力

40%二甲戊·乙乳油防除玉米田杂草田间药效试验

田间试验表明：40%二甲戊.乙乳油150～200mL/667m^2能有效地防除玉米田中的杂草,药后15d、30d、45d对禾本科杂草和阔叶杂草的株防效达95.2%、96.1%、98.1%,药后45d鲜重防效达98.5

期刊

二甲戊乐·乙乳油玉米杂草防治效果

Strong Completeness of Medium Logic System

The strong completeness of medium logic system is discussed. The following results are proved: medium propositional logic system MP and its extension MP * are s

期刊

ML媒介逻辑连贯性可靠性MPMedium logic Formal system Consistency Weak completeness

Executive Stock Option, Mediation of Agency Costs and Allocation of Power in Levered Firms

The relationship between options and agency costs in levered firms is studied by modeling the effect of executive stock options on the managers investment str

期刊

认股权执行程序预购股票价格政府部门债务Executive stock options Exercise price Agency costs Le

Propagating Characteristics of Confocal Elliptical Waveguide Filled with Multilayered Dielectrics

Using the method of separation of variables in the elliptical coordinate system, a recursive formula for the electromagnetic fields in a confocal elliptical wav

期刊

电磁场马蒂厄函数传递常数共焦椭圆波导本征频率Electromagnetic field Mathieu function Propagating

强化职工培训促进企业腾飞

强化职工培训促进企业腾飞夏学海，徐吉美江苏汇中集团（公司）在“坚持眼睛向内，加大职教投入，造就一流队伍，建设一而企业”决策的指导下，围绕企业发展目标，拟订人才需求计划，成立职教工

期刊

职工培训企业发展目标江苏省专业人才企业腾飞国际贸易人才市场营销特殊贡献职工教育微机应用

Improved Space-Time Selective Interference Cancellation Scheme for CDMA Systems

Space-time selective parallel interference cancellation(ST-SPIC) is a computationally effective approach combining multiuser detection (MUD) with antenna array

期刊

码分多址系统CDMA时空选择干涉抵消图自适应矩阵移动通信selective parallel interference cancellation a

A New Algorithm for Mining Frequent Pattern

Mining frequent pattern in transaction database, time-series databases, and many other kinds of databases have been studied popularly in data mining research. M

期刊

算法重复模式案数据库FP树FP路径data mining algorithm frequent pattern set FPgrowth

Remarks on the Riesz Separation Property of the Linear Span of Positive Compact Operators

It is proven that there exists a Dedekind complete Banach lattice E such that the linear spans Kr (E) and Wr (E) of positive compact and positive weakly compact

期刊

线性范围数学巴拿赫格代数Banach lattice Dcdekind complete Compact operator Riesz separ