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

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, A bi-criteria optimization model for medical device sterilization, A survey on the structure of approximation classes, Bridging gap between standard and differential polynomial approximation: The case of bin-packing, Approximability of scheduling with fixed jobs, Approximation schemes for packing with item fragmentation, An asymptotic approximation scheme for the concave cost bin packing problem, A 5/4 linear time bin packing algorithm, Resource allocation algorithms for virtualized service hosting platforms, On bin packing with clustering and bin packing with delays, Best fit bin packing with random order revisited, Online algorithms with advice for bin packing and scheduling problems, A fundamental restriction on fully dynamic maintenance of bin packing, An improved approximation scheme for variable-sized bin packing, On approximating the longest path in a graph, \(\varepsilon \)-optimization schemes and \(L\)-bit precision: alternative perspectives for solving combinatorial optimization problems, A polynomial algorithm for an integer quadratic non-separable transportation problem, Colocating tasks in data centers using a side-effects performance model, Multidimensional cube packing, An approximation algorithm for square packing., Asymptotic fully polynomial approximation schemes for variants of open-end bin packing, The two-dimensional cutting stock problem revisited, Class constrained bin packing revisited, Constructive heuristics for the canister filling problem, Min-sum bin packing, On the approximability of the two-phase knapsack problem, More on batched bin packing, Fully dynamic bin packing revisited, Bin packing with controllable item sizes, Scalable optimal deployment in the cloud of component-based applications using optimization modulo theory, mathematical programming and symmetry breaking, A robust APTAS for the classical bin packing problem, An asymptotic PTAS for batch scheduling with nonidentical job sizes to minimize makespan, Bidimensional packing by bilinear programming, Three-dimensional packings with rotations, Variable sized online interval coloring with bandwidth, Hardness of approximation for orthogonal rectangle packing and covering problems, Differential approximation algorithms for some combinatorial optimization problems, More on ordered open end bin packing, Feasibility criteria for high-multiplicity partitioning problems, An almost optimal approximation algorithm for monotone submodular multiple knapsack, A sublinear-time approximation scheme for bin packing, Approximation algorithms for orthogonal packing problems for hypercubes, On lazy bin covering and packing problems, Bounded-space online bin cover, A linear time algorithm for restricted bin packing and scheduling problems, Techniques and results on approximation algorithms for packing circles, From packing rules to cost-sharing mechanisms, Truthful mechanism design for bin packing with applications on cloud computing, Two-dimensional packing problems: a survey, Linear time-approximation algorithms for bin packing, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems, On dependent randomized rounding algorithms, Combinatorial analysis (nonnegative matrices, algorithmic problems), Online results for black and white bin packing, A linear time bin-packing algorithm, Scheduling with an orthogonal resource constraint, A PTAS for the multiple subset sum problem with different knapsack capacities, Locality-preserving allocations problems and coloured bin packing, An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing, New approximability results for two-dimensional bin packing, Online bin packing with advice

Cites Work