Bin packing can be solved within 1 + ε in linear time

1981/12/01 by W. Fernandez de la Véga, W. Fernandez de la Vega, George S. Lueker +1 · 7 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Bin #Bin packing problem #Combinatorics #Discrete mathematics #Mathematics #Optimization and Packing Problems #Unit (ring theory) #graph theory and CDMA systems

paper · doi:10.1007/bf02579456

crossref issued 1981/12/01 · crossref published 1981/12/01 · crossref published-print 1981/12/01 · openalex publication_date 1981/12/01 · crossref created 2007/03/22 · crossref deposited 2019/05/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31 · crossref indexed 2026/08/05

Citations

• Mathematical Methods of Organizing and Planning Production
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• A Linear Programming Approach to the Cutting-Stock Problem
• Reducibility among Combinatorial Problems

Cited by

• The two-dimensional cutting stock problem revisited
• An approximation notion between P and FPTAS
• Overcommitment in Cloud Services: Bin Packing with Chance Constraints
• Power-efficient Assignment of Virtual Machines to Physical Machines
• Proof verification and the hardness of approximation problems
• Proof verification and hardness of approximation problems
• Bin packing problem [wikipedia]