Parallel approximation schemes for subset sum and knapsack problems (Q1084863): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 02:09, 5 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Parallel approximation schemes for subset sum and knapsack problems |
scientific article |
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
