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

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, Worst-case analysis of a new heuristic for the travelling salesman problem, A Counterexample to a Bin Packing Conjecture, On the generalized bin packing problem, Lower bounds for batched bin packing, Constant-Ratio Approximation for Robust Bin Packing with Budgeted Uncertainty, Linear waste of best fit bin packing on skewed distributions, Online Bin Packing with Advice of Small Size, List-scheduling and column-generations for scheduling of n job-groups with set up time and due date through m identical parallel machines to minimize makespan, Selfish Vector Packing, On two dimensional packing, Parametric Lower Bound for On-Line Bin-Packing, Online algorithms for 1-space bounded multidimensional bin packing and hypercube packing, A note on a selfish bin packing problem, Multi-machine energy-aware scheduling, Approximation and online algorithms for multidimensional bin packing: a survey, Heuristics with Constant Error Guarantees for the Multi Center Capacitated Minimum Spanning Tree Problem, Lower bounds on the performance of online algorithms for relaxed packing problems, Logic-Based Benders Decomposition and Binary Decision Diagram Based Approaches for Stochastic Distributed Operating Room Scheduling, On Lagrangian relaxation for constrained maximization and reoptimization problems, A reinforcement learning iterated local search for makespan minimization in additive manufacturing machine scheduling problems, Compact integer linear programming formulations for the temporal bin packing problem with fire-ups, Single batch machine scheduling with dual setup times for autoclave molding manufacturing, Mathematical models and approximate solution approaches for the stochastic bin packing problem, An iteratively doubling local search for the two-dimensional irregular bin packing problem with limited rotations, On-line bin packing ? A restricted survey, Online bin packing with cardinality constraints resolved, Bin packing problem with scenarios, A mixed‐integer linear programming model and a metaheuristic approach for the selection and allocation of land parcels problem, A study on load-balanced variants of the bin packing problem, Equitable scheduling on a single machine, Pareto optimal equilibria for selfish bin packing with uniform cost sharing, Drawer algorithms for 1-space bounded multidimensional hyperbox packing, Using weight decision for decreasing the price of anarchy in selfish bin packing games, Relative Worst-Order Analysis: A Survey, The effect of different mathematical formulations on a matheuristic algorithm for the production routing problem, Bin packing with general cost structures, An improved approximation algorithm for a scheduling problem with transporter coordination, Online two-dimensional vector packing with advice, An improved algorithm for parallel machine scheduling under additional resource constraints, Comparing online algorithms for bin packing problems, Efficient algorithms for the offline variable sized bin-packing problem, Efficient 1-space bounded hypercube packing algorithm, Parallel online algorithms for the bin packing problem, On online algorithms for bin, strip, and box packing, and their worst-case and average-case analysis, Interior-Point-Based Online Stochastic Bin Packing, A bin packing game with cardinality constraints under the best cost rule, Fully-Dynamic Bin Packing with Little Repacking, Sparse, Continuous Policy Representations for Uniform Online Bin Packing via Regression of Interpolants, Online Algorithm for 1-Space Bounded Multi-dimensional Bin Packing, Online bin packing of squares and cubes, Average-case analyses of first fit and random fit bin packing, Online bin packing with arbitrary release times, The class constrained bin packing problem with applications to video-on-demand, Scheduling a single batch processing machine with non-identical job sizes, Online bin packing of squares and cubes, Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families, Bin packing problems with rejection penalties and their dual problems, Scheduling advertisements on a web page to maximize revenue, Lower bounds for several online variants of bin packing, An improved mechanism for selfish bin packing, Online algorithms for page replication in rings, On the Bahncard problem, The maximum resource bin packing problem, Fully dynamic bin packing revisited, ONE-SPACE BOUNDED ALGORITHMS FOR TWO-DIMENSIONAL BIN PACKING, Upper bounds for heuristic approaches to the strip packing problem, A new lower bound for classic online bin packing, Several methods of analysis for cardinality constrained bin packing, Unnamed Item, Unnamed Item, Analysis of Stochastic Online Bin Packing Processes, Batch scheduling of nonidentical job sizes with minsum criteria, Better Bin Packing Approximations via Discrepancy Theory, Quality of strong equilibria for selfish bin packing with uniform cost sharing, A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems, NP-Complete operations research problems and approximation algorithms, Best Fit Bin Packing with Random Order Revisited, Approximation algorithms for the design of SDH/SONET networks, Integer programming duality: Price functions and sensitivity analysis, Online bin packing with advice of small size, Approximation scheduling algorithms: a survey, Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps, From packing rules to cost-sharing mechanisms, A tight approximation algorithm for problem \(P2\rightarrow D|v=1,c=1|C_{\max }\), A lower bound for online rectangle packing, AN EFFICIENT JOB SCHEDULING ALGORITHM IN PARTITIONABLE MESH CONNECTED SYSTEMS, Online square and cube packing, Unnamed Item, Online results for black and white bin packing, NF-Based Algorithms for Online Bin Packing with Buffer and Item Size Limitation, Online Bin Packing with (1,1) and (2,R) Bins, OPTIMAL STATIC ASSIGNMENT AND ROUTING POLICIES FOR SERVICE CENTERS WITH CORRELATED TRAFFIC, On Packing Two-Dimensional Bins, Locality-preserving allocations problems and coloured bin packing, The tight absolute bound of First Fit in the parameterized case, Online bin packing with \((1,1)\) and \((2,R)\) bins, NF-based algorithms for online bin packing with buffer and bounded item size, A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing