Parallel approximation schemes for subset sum and knapsack problems (Q1084863)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3980482
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Parallel approximation schemes for subset sum and knapsack problems |
scientific article; zbMATH DE number 3980482 |
Statements
Parallel approximation schemes for subset sum and knapsack problems (English)
0 references
1987
0 references
This paper presents parallel approximation schemes for the Subset Sum, 0- 1 Knapsack, and several other optimization problems. These algorithms offer a three-way trade-off among parallel time, the accuracy of the solution and the number of processors used. The maximum numbers of processors which can be usefully employed depend on n (the size of the input), and the accuracy requirement \(\epsilon\). The parallel running times of the algorithms are polynomial in both log n and log(1/\(\epsilon)\) when enough processors are used.
0 references
optimization problems
0 references
maximum numbers of processors
0 references
parallel running times
0 references
parallel algorithms
0 references
0.8782769441604614
0 references
0.8503857851028442
0 references
0.8501706123352051
0 references
