Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

DOI10.1137/0203025zbMath0297.68028OpenAlexW2043862089MaRDI QIDQ4051589

Jeffrey D. Ullman, Michael R. Garey, Alan Demers, David S. Johnson, Ronald L. Graham

Publication date: 1975

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/318575adfb030622ba709d257b459afa108b8526

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99) Software, source code, etc. for problems pertaining to combinatorics (05-04)

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

Deep performance analysis of refined harmonic bin packing algorithm ⋮ Lower bounds for on-line graph coloring ⋮ On-line scheduling of jobs with fixed start and end times ⋮ A 71/60 theorem for bin packing ⋮ Heuristic evaluation techniques for bin packing approximation algorithms ⋮ 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 ⋮ The fleet size and mix vehicle routing problem ⋮ Shelf algorithms for on-line strip packing ⋮ Online bin packing with overload cost ⋮ Algorithms for on-line bin-packing problems with cardinality constraints ⋮ A biased random-key genetic algorithm to maximize the number of accepted lightpaths in WDM optical networks ⋮ On the worst-case ratio of a compound multiprocessor scheduling algorithm ⋮ Bin packing problems in one dimension: Heuristic solutions and confidence intervals ⋮ Bin packing with rejection revisited ⋮ The average-case analysis of some on-line algorithms for bin packing ⋮ Bin packing with divisible item sizes ⋮ Computing redundant resources for the resource constrained project scheduling problem ⋮ Sink location to find optimal shelters in evacuation planning ⋮ BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem ⋮ An AFPTAS for variable sized bin packing with general activation costs ⋮ Worst-case performance analysis of some approximation algorithms for minimizing makespan and flowtime ⋮ Worst-case analysis of fast heuristics for packing squares into a square ⋮ Online variable-sized bin packing ⋮ Worst-case analysis of the FFH algorithm for online variable-sized bin packing ⋮ Exact and approximate methods for a one-dimensional minimax bin-packing problem ⋮ Tight performance bound of \(AFBk\) bin packing ⋮ Average-case analysis of the smart next fit algorithm ⋮ Expected performance of the shelf heuristic for 2-dimensional packing ⋮ Edge disjoint Polyp Packing ⋮ Two- and three-dimensional parametric packing ⋮ Tighter bounds of the First Fit algorithm for the bin-packing problem ⋮ Parallel approximation algorithms for bin packing ⋮ An on-line graph coloring algorithm with sublinear performance ratio ⋮ Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem ⋮ Bin packing with ``largest in bottom constraint: tighter bounds and generalizations ⋮ Bin packing under linear constraints ⋮ Maximizing the minimum load: the cost of selfishness ⋮ Selfish bin packing with cardinality constraints ⋮ Bin packing: Maximizing the number of pieces packed ⋮ Single-machine scheduling with periodic maintenance to minimize makespan revisited ⋮ On linear lower bounds for the resource constrained project scheduling problem. ⋮ A note on online hypercube packing ⋮ A lower bound for on-line bin packing ⋮ An improved BL lower bound ⋮ Parametric on-line algorithms for packing rectangles and boxes. ⋮ Probabilistic analysis for simple one- and two-dimensional bin packing algorithms ⋮ Bin packing game with a price of anarchy of \(\frac{3}{2}\) ⋮ Offline first-fit decreasing height scheduling of power loads ⋮ On the absolute approximation ratio for first fit and related results ⋮ Worst-case analysis of the subset sum algorithm for bin packing. ⋮ Bin packing can be solved within 1+epsilon in linear time ⋮ Bridging gap between standard and differential polynomial approximation: The case of bin-packing ⋮ Assembly line balancing as generalized bin packing ⋮ Scheduling batch processing machine using max-min ant system algorithm improved by a local search method ⋮ Best fit bin packing with random order revisited ⋮ Selfish vector packing ⋮ Bin packing with fragmentable items: presentation and approximations ⋮ Product packing and stacking under uncertainty: a robust approach ⋮ A new version of on-line variable-sized bin packing ⋮ The intermediate price of anarchy (IPoA) in bin packing games ⋮ Approximation algorithms for time constrained scheduling ⋮ Matheuristics for the irregular bin packing problem with free rotations ⋮ A hybrid feasibility constraints-guided search to the two-dimensional bin packing problem with due dates ⋮ A generalized bin packing problem for parcel delivery in last-mile logistics ⋮ Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem ⋮ Cutting stock problems with nondeterministic item lengths: a new approach to server consolidation ⋮ Online packing of arbitrary sized items into designated and multipurpose bins ⋮ Repacking helps in bounded space on-line bin-packing ⋮ Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts ⋮ Resource augmented semi-online bounded space bin packing ⋮ Recent advances on two-dimensional bin packing problems ⋮ Tight results for next fit and worst fit with resource augmentation ⋮ Polynomial approximation algorithms with performance guarantees: an introduction-by-example ⋮ Vehicle minimization for periodic deliveries ⋮ Two-dimensional online bin packing with rotation ⋮ Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem ⋮ More on batched bin packing ⋮ Resource constrained scheduling as generalized bin packing ⋮ Online algorithms for 1-space bounded 2-dimensional bin packing and square packing ⋮ Approximation algorithm for the oriented two-dimensional bin packing problem ⋮ A note on online strip packing ⋮ Heuristic methods and applications: A categorized survey ⋮ Bin packing with restricted piece sizes ⋮ Average-case analysis of the modified harmonic algorithm ⋮ Three-dimensional orthogonal graph drawing algorithms ⋮ Bin packing and multiprocessor scheduling problems with side constraint on job types ⋮ New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems ⋮ Market-based pricing in grids: on strategic manipulation and computational cost ⋮ A \(17/10\)-approximation algorithm for \(k\)-bounded space on-line variable-sized bin packing ⋮ Applying extra-resource analysis to load balancing. ⋮ A storage-size selection problem ⋮ Linear time-approximation algorithms for bin packing ⋮ Two-dimensional rectangle packing: On-line methods and results ⋮ Convergence of optimal stochastic bin packing ⋮ An O(n) bin-packing algorithm for uniformly distributed data ⋮ A branch-and-bound algorithm for the two-dimensional vector packing problem ⋮ Algorithms for the variable sized bin packing problem ⋮ Parametric packing of selfish items and the subset sum algorithm ⋮ A bin packing problem with over-sized items

This page was built for publication: Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms