Laboratoire TIM3, INP - Grenoble, F-38031, Grenoble Cedex, France
ENS - Lyon, Fontenay, France
Abstract:
The advent of parallel machines brought about a controverse in the domain of parallel algorithms: is it worth to conceive parallel algorithms for NP-complete problems? In this work we present a parallel implementation of a sequential algorithm from Horowitz and Sahni for the knapsack problem on a FPS T20. Our aim is to establish some experimental results in order to allow comparisons for forthcoming works. The results show that the development of theory and technology yields the computation tractability of very large knapsack problems.