PARALLEL APPROXIMATE ALGORITHMS FOR THE 0-1 KNAPSACK PROBLEM.

P. S. Gopalakrishnan; I. V. Ramakrishnan; L. N. Kanal

PARALLEL APPROXIMATE ALGORITHMS FOR THE 0-1 KNAPSACK PROBLEM.

P. S. Gopalakrishnan
, I. V. Ramakrishnan
, L. N. Kanal

Computer Science

Stony Brook University

University of Maryland, College Park

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

6 Scopus citations

Abstract

An approximate algorithm is presented for the 0-1 knapsack problem on the parallel random access machine model. The algorithm takes epsilon 0 less than epsilon less than 1, as an input parameter and finds a solution such that the ratio of its deviation from the optimal solution is at most epsilon . The algorithm requires O(log**3 n plus log**2 nlog (1/ epsilon ) time and uses at most n**2 **. **5 / epsilon **1 **. **5 processors. In contrast to a naive algorithm that requires significantly more processors, the authors' algorithm exploits the relationship among the sets of solutions to the problem generated in the intermediate steps to reduce the number of solutions considered. This in turn results in a reduction in the processor requirements.

Original language	English
Title of host publication	Proceedings of the International Conference on Parallel Processing
Editors	Kai Hwang, Steven M. Jacobs, Earl E. Swartzlander
Publisher	IEEE
Pages	444-451
Number of pages	8
ISBN (Print)	0818607246
State	Published - 1986

Publication series

Name	Proceedings of the International Conference on Parallel Processing

Cite this

@inproceedings{f346658f946440dd96bc18b7761906db,

title = "PARALLEL APPROXIMATE ALGORITHMS FOR THE 0-1 KNAPSACK PROBLEM.",

abstract = "An approximate algorithm is presented for the 0-1 knapsack problem on the parallel random access machine model. The algorithm takes epsilon 0 less than epsilon less than 1, as an input parameter and finds a solution such that the ratio of its deviation from the optimal solution is at most epsilon . The algorithm requires O(log**3 n plus log**2 nlog (1/ epsilon ) time and uses at most n**2 **. **5 / epsilon **1 **. **5 processors. In contrast to a naive algorithm that requires significantly more processors, the authors' algorithm exploits the relationship among the sets of solutions to the problem generated in the intermediate steps to reduce the number of solutions considered. This in turn results in a reduction in the processor requirements.",

author = "Gopalakrishnan, \{P. S.\} and Ramakrishnan, \{I. V.\} and Kanal, \{L. N.\}",

year = "1986",

language = "English",

isbn = "0818607246",

series = "Proceedings of the International Conference on Parallel Processing",

publisher = "IEEE",

pages = "444--451",

editor = "Kai Hwang and Jacobs, \{Steven M.\} and Swartzlander, \{Earl E.\}",

booktitle = "Proceedings of the International Conference on Parallel Processing",

}

PARALLEL APPROXIMATE ALGORITHMS FOR THE 0-1 KNAPSACK PROBLEM. / Gopalakrishnan, P. S.; Ramakrishnan, I. V.; Kanal, L. N.
Proceedings of the International Conference on Parallel Processing. ed. / Kai Hwang; Steven M. Jacobs; Earl E. Swartzlander. IEEE, 1986. p. 444-451 (Proceedings of the International Conference on Parallel Processing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - PARALLEL APPROXIMATE ALGORITHMS FOR THE 0-1 KNAPSACK PROBLEM.

AU - Gopalakrishnan, P. S.

AU - Ramakrishnan, I. V.

AU - Kanal, L. N.

PY - 1986

Y1 - 1986

N2 - An approximate algorithm is presented for the 0-1 knapsack problem on the parallel random access machine model. The algorithm takes epsilon 0 less than epsilon less than 1, as an input parameter and finds a solution such that the ratio of its deviation from the optimal solution is at most epsilon . The algorithm requires O(log**3 n plus log**2 nlog (1/ epsilon ) time and uses at most n**2 **. **5 / epsilon **1 **. **5 processors. In contrast to a naive algorithm that requires significantly more processors, the authors' algorithm exploits the relationship among the sets of solutions to the problem generated in the intermediate steps to reduce the number of solutions considered. This in turn results in a reduction in the processor requirements.

AB - An approximate algorithm is presented for the 0-1 knapsack problem on the parallel random access machine model. The algorithm takes epsilon 0 less than epsilon less than 1, as an input parameter and finds a solution such that the ratio of its deviation from the optimal solution is at most epsilon . The algorithm requires O(log**3 n plus log**2 nlog (1/ epsilon ) time and uses at most n**2 **. **5 / epsilon **1 **. **5 processors. In contrast to a naive algorithm that requires significantly more processors, the authors' algorithm exploits the relationship among the sets of solutions to the problem generated in the intermediate steps to reduce the number of solutions considered. This in turn results in a reduction in the processor requirements.

UR - https://www.scopus.com/pages/publications/0022901354

M3 - Conference contribution

SN - 0818607246

T3 - Proceedings of the International Conference on Parallel Processing

SP - 444

EP - 451

BT - Proceedings of the International Conference on Parallel Processing

A2 - Hwang, Kai

A2 - Jacobs, Steven M.

A2 - Swartzlander, Earl E.

PB - IEEE

ER -

PARALLEL APPROXIMATE ALGORITHMS FOR THE 0-1 KNAPSACK PROBLEM.

Abstract

Publication series

Other files and links

Fingerprint

Cite this