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

DOI10.1007/BF02579456zbMath0485.68057OpenAlexW2145028977WikidataQ56212224 ScholiaQ56212224MaRDI QIDQ1164429

Wenceslas Fernandez de la Vega, George S. Lueker

Publication date: 1981

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579456

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of packing and covering (05B40) Discrete mathematics in relation to computer science (68R99)

Related Items (only showing first 100 items - show all)

Approximation algorithms for distance constrained vehicle routing problems ⋮ An efficient heuristic method for the simple assembly line balancing problem ⋮ Constant-Ratio Approximation for Robust Bin Packing with Budgeted Uncertainty ⋮ Multiple subset sum with inclusive assignment set restrictions ⋮ On dependent randomized rounding algorithms ⋮ A two-dimensional vector packing model for the efficient use of coil cassettes ⋮ A note on the approximability of cutting stock problems ⋮ Batched bin packing revisited ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ A note on a variant of the online open end bin packing problem ⋮ Parameterized complexity of configuration integer programs ⋮ High-multiplicity \(N\)-fold IP via configuration LP ⋮ Tight approximation algorithms for geometric bin packing with skewed items ⋮ EPTAS for the dual of splittable bin packing with cardinality constraint ⋮ There is no APTAS for 2-dimensional vector bin packing: revisited ⋮ A 4/3-APPROXIMATION ALGORITHM FOR CASSETTE PACKING IN STEEL INDUSTRY ⋮ A study on load-balanced variants of the bin packing problem ⋮ Scheduling with Interjob Communication on Parallel Processors ⋮ A 4/3 OPT+2/3 approximation for big two-bar charts packing problem ⋮ Approximation schemes for packing splittable items with cardinality constraints ⋮ Bin packing with general cost structures ⋮ Priority-based bin packing with subset constraints ⋮ Online two-dimensional vector packing with advice ⋮ Unnamed Item ⋮ Windows scheduling of arbitrary-length jobs on multiple machines ⋮ On-line bin packing with restricted repacking ⋮ Fast Approximation Methods for Online Scheduling of Outpatient Procedure Centers ⋮ Bin covering with cardinality constraints ⋮ Note on non-uniform bin packing games ⋮ Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP ⋮ A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem ⋮ Online bin packing of squares and cubes ⋮ Set Covering with Ordered Replacement: Additive and Multiplicative Gaps ⋮ Two-dimensional bin packing with one-dimensional resource augmentation ⋮ A fast asymptotic approximation scheme for bin packing with rejection ⋮ The class constrained bin packing problem with applications to video-on-demand ⋮ A one-dimensional bin packing problem with shelf divisions ⋮ A 3-approximation algorithm for two-dimensional bin packing ⋮ Online bin packing of squares and cubes ⋮ Lower bounds and algorithms for the 2-dimensional vector packing problem ⋮ Hedging uncertainty: approximation algorithms for stochastic optimization problems ⋮ Bin packing problems with rejection penalties and their dual problems ⋮ Unnamed Item ⋮ Minimum Weighted Sum Bin Packing ⋮ Approximation Schemes for Packing Splittable Items with Cardinality Constraints ⋮ Near-Optimal Algorithms for the Assortment Planning Problem Under Dynamic Substitution and Stochastic Demand ⋮ Several methods of analysis for cardinality constrained bin packing ⋮ Unnamed Item ⋮ An approximation scheme for bin packing with conflicts ⋮ Streaming algorithms for bin packing and vector scheduling ⋮ Better Bin Packing Approximations via Discrepancy Theory ⋮ Approximation Schemes for Machine Scheduling with Resource (In-)dependent Processing Times ⋮ A Survey on Approximation Algorithms for Scheduling with Machine Unavailability ⋮ Best Fit Bin Packing with Random Order Revisited ⋮ A Robust AFPTAS for Online Bin Packing with Polynomial Migration ⋮ Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps ⋮ Unnamed Item ⋮ Several methods of analysis for cardinality constrained bin packing ⋮ Adaptive Bin Packing with Overflow ⋮ Offline black and white bin packing ⋮ Approximation schemes for knapsack problems with shelf divisions ⋮ An improved two-machine flowshop scheduling with intermediate transportation ⋮ Vertex cover meets scheduling ⋮ A 71/60 theorem for bin packing ⋮ Bin packing as a random walk: A note on Knödel's paper ⋮ Partially dynamic bin packing can be solved within \(1 + \varepsilon\) in (amortized) polylogarithmic time ⋮ An APTAS for bin packing with clique-graph conflicts ⋮ Rectangle packing with one-dimensional resource augmentation ⋮ Multiple-type, two-dimensional bin packing problems: Applications and algorithms ⋮ There is no asymptotic PTAS for two-dimensional vector packing ⋮ Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem ⋮ Strip packing with precedence constraints and strip packing with release times ⋮ Scheduling with interjob communication on parallel processors ⋮ Bin packing with divisible item sizes and rejection penalties ⋮ New approximation algorithms for the unsplittable capacitated facility location problem ⋮ Semi-on-line bin packing: a short overview and a new lower bound ⋮ Polynomial time approximation schemes for class-constrained packing problems ⋮ Bin packing with rejection revisited ⋮ The average-case analysis of some on-line algorithms for bin packing ⋮ Polynomial-time approximation schemes for circle and other packing problems ⋮ Minimizing the number of stations and station activation costs for a production line ⋮ A polynomial-time approximation scheme for maximizing the minimum machine completion time ⋮ An AFPTAS for variable sized bin packing with general activation costs ⋮ Worst-case performance analysis of some approximation algorithms for minimizing makespan and flowtime ⋮ A memetic algorithm for the cost-oriented robotic assembly line balancing problem ⋮ Approximation schemes for Euclidean vehicle routing problems with time windows ⋮ On relocation problems with multiple identical working crews ⋮ Tight approximations for resource constrained scheduling and bin packing ⋮ Lower bounds on the performance of online algorithms for relaxed packing problems ⋮ Edge disjoint Polyp Packing ⋮ Parallel approximation algorithms for bin packing ⋮ An approximation scheme for strip packing of rectangles with bounded dimensions ⋮ Bin packing under linear constraints ⋮ An approximation scheme for scheduling independent jobs into subcubes of a hypercube of fixed dimension ⋮ A quantization framework for smoothed analysis of Euclidean optimization problems ⋮ An asymptotic competitive scheme for online bin packing ⋮ Approximate strong separation with application in fractional graph coloring and preemptive scheduling. ⋮ Exact algorithms for the guillotine strip cutting/packing problem. ⋮ Vector bin packing with multiple-choice ⋮ An approximation scheme for the two-stage, two-dimensional knapsack problem

Cites Work

This page was built for publication: Bin packing can be solved within 1+epsilon in linear time