Parallel time and space upper-bounds for the subset-sum problem

DOI10.1016/j.tcs.2008.06.051zbMath1152.68057OpenAlexW1984941464MaRDI QIDQ955010

Carlos Alberto Alonso Sanches, Nei Yoshihiro Soma, Horacio Hideki Yanasse

Publication date: 18 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.06.051

zbMATH Keywords

dynamic programmingknapsack problemparallel algorithmssubset-sum problemupper-bound complexity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Dynamic programming (90C39) Parallel algorithms in computer science (68W10)

Related Items (4)

Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ A low-space algorithm for the subset-sum problem on GPU ⋮ An improved balanced algorithm for the subset-sum problem ⋮ Applications of mathematics to maritime search

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An efficient parallel algorithm for solving the knapsack problem on hypercubes
• An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem
• An introduction to parallelism in combinatorial optimization
• A randomized linear-work EREW PRAM algorithm to find a minimum spanning forest
• Parallel Merge Sort
• Computing Partitions with Applications to the Knapsack Problem
• o(log⁴ n) time parallel maximal matching algorithm using linear number of processors
• An exact algorithm for the subset sum problem

This page was built for publication: Parallel time and space upper-bounds for the subset-sum problem