Parallel approximation schemes for subset sum and knapsack problems (Q1084863): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
ReferenceBot (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Parallelism in random access machines / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4198056 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3892056 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3907409 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3050129 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3898034 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Exact and Approximate Algorithms for Scheduling Nonidentical Processors / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: General approximation algorithms for some arithmetical combinatorial problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Parallel approximation schemes for subset sum and knapsack problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Algorithms for Scheduling Independent Tasks / rank
 
Normal rank
Property / cites work
 
Property / cites work: Combinatorial Problems: Reductibility and Approximation / rank
 
Normal rank

Latest revision as of 16:44, 17 June 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
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references