Parallel approximation algorithms for bin packing

DOI10.1016/0890-5401(89)90003-5zbMath0677.90054OpenAlexW1988727224MaRDI QIDQ1123807

Ernst W. Mayr, Richard J. Anderson, Manfred K. Warmuth

Publication date: 1989

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(89)90003-5

zbMATH Keywords

bin packingpolynomial approximation algorithmsparallel complexity of polynomial heuristics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27) Parallel numerical computation (65Y05) Theory of operating systems (68N25)

Related Items

A theory of strict P-completeness ⋮ Almost fully-parallel parentheses matching ⋮ The iterated mod problem ⋮ A 5/4 linear time bin packing algorithm ⋮ A fundamental restriction on fully dynamic maintenance of bin packing ⋮ A parallel algorithm to construct a dominance graph on nonoverlapping rectangles ⋮ Matching parentheses in parallel ⋮ Optimal merging and sorting on the EREW PRAM ⋮ Parallel multiple search ⋮ A theory of strict P-completeness ⋮ Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps ⋮ Space-efficient parallel merging ⋮ An optimal parallel algorithm for merging using multiselection

Cites Work

• Bin packing can be solved within 1+epsilon in linear time
• The maximum flow problem is log space complete for P
• Linear programming is log-space hard for P
• A new proof for the first-fit decreasing bin-packing algorithm
• Optimal parallel generation of a computation tree form
• Parallel Prefix Computation
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Parallelism in random access machines
• Parallel Processing with the Perfect Shuffle