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

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

An Optimal Parallel Algorithm for the Knapsack Problem Based on EREW

其他学术论文