𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Fast and Scalable Parallel Algorithms for Knapsack-like Problems

✍ Scribed by Afonso Ferreira; John Michael Robson

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
403 KB
Volume
39
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

We present two new algorithms for searching in sorted X Ψ‰ Y Ψ‰ R Ψ‰ S, one based on heaps and the other on sampling. Each of the algorithms runs in time O(n 2 log n) (n being the size of the sorted arrays X, Y, R, and S). Hence in each case, by constructing arrays of size n ‫؍‬ O(2 s/4 ), we obtain a new algorithm for solving certain NP-complete problems such as knapsack on s data items in time equal (up to a constant factor) to the best algorithm currently known. Each of the algorithms is capable of being efficiently implemented in parallel and so solving large instances of these NP-complete problems fast on coarse-grained distributed memory parallel computers. The parallel version of the heap based algorithm is communicationefficient and exhibits optimal speedup for a number of processors less than n using O(n) space in each one; the sampling based algorithm exhibits optimal speedup for any number of processors up to n using O(n) space in total provided that the architecture is capable of logarithmic time sorting.

πŸ“œ SIMILAR VOLUMES

Parallel Algorithms for Orthotropic Prob
Parallel Algorithms for Orthotropic Problems
✍ Ivar Gustafsson; Gunhild Lindskog πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 784 KB

Finite element meshes and node-numberings suitable for parallel solution with equally loaded processors are presented for linear orthotropic elliptic partial differential equations. These problems are of great importance, for instance in the oil and airfoil industries. The linear systems of equation

Multilevel fast multipole algorithm enha
Multilevel fast multipole algorithm enhanced by GPU parallel technique for electromagnetic scattering problems
✍ Kan Xu; Da Zhi Ding; Zheng Hong Fan; Ru Shan Chen πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 187 KB

## Abstract Along with the development of graphics processing Units (GPUS) in floating point operations and programmability, GPU has increasingly become an attractive alternative to the central processing unit (CPU) for some of compute‐intensive and parallel tasks.In this article, the multilevel fa

Parallel Output-Sensitive Algorithms for
Parallel Output-Sensitive Algorithms for Combinatorial and Linear Algebra Problems
✍ John H. Reif πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 160 KB

This paper gives output-sensitive parallel algorithms whose performance depends on the output size and are significantly more efficient tan previous algorithms for problems with sufficiently small output size. Inputs are n\_n matrices over a fixed ground field. Let P(n) and M(n) be the PRAM processo

Parallel Algorithms for the Edge-Colorin
Parallel Algorithms for the Edge-Coloring and Edge-Coloring Update Problems
✍ Weifa Liang; Xiaojun Shen; Qing Hu πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 342 KB

In fact, Vizing's proof implies an O(nm) time algorithm with ⌬ Ο© 1 colors for the edge-coloring problem. However, Holyer has shown that deciding whether a graph requires ⌬ or ⌬ Ο© 1 colors is NP-complete [10]. For a multigraph G, Shannon showed that Ј(G) Υ… 3⌬/2 [16]. A number of parallel algorithms