The average-case analysis of some on-line algorithms for bin packing
From MaRDI portal
Publication:1100912
DOI10.1007/BF02579171zbMath0641.68096OpenAlexW2009931551MaRDI QIDQ1100912
Publication date: 1986
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02579171
Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of packing and covering (05B40) Discrete mathematics in relation to computer science (68R99)
Related Items
Linear waste of best fit bin packing on skewed distributions ⋮ Asymptotics for transportation cost in high dimensions ⋮ Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck ⋮ Expected performance of the shelf heuristic for 2-dimensional packing ⋮ A tight lower bound for optimal bin packing ⋮ Optimal Matching and Empirical Measures ⋮ A concentration inequality for the facility location problem ⋮ Average-case competitive analyses for one-way trading ⋮ Randomized algorithms for the on-line minimum matching problem on euclidean space ⋮ Average performance of greedy heuristics for the integer knapsack problem. ⋮ On online algorithms for bin, strip, and box packing, and their worst-case and average-case analysis ⋮ Gravitational allocation for uniform points on the sphere ⋮ Interior-Point-Based Online Stochastic Bin Packing ⋮ Best fit bin packing with random order revisited ⋮ Average-case analyses of first fit and random fit bin packing ⋮ Packings in two dimensions: Asymptotic average-case analysis of algorithms ⋮ Quantum information processing: The case of vanishing interaction energy ⋮ Average-case performance analysis of a 2D strip packing algorithm -- NFDH ⋮ Unnamed Item ⋮ Average-case analysis of cutting and packing in two dimensions ⋮ Analysis of Stochastic Online Bin Packing Processes ⋮ Stochastic on-line knapsack problems ⋮ Tight bounds for minimax grid matching with applications to the average case analysis of algorithms ⋮ Filling random cycles ⋮ How modeling can attract experimentalists to improve solar cell's efficiency: Divide-and-conquer approach ⋮ A provably efficient algorithm for dynamic storage allocation ⋮ Exact Bounds for the Stochastic Upward Matching Problem ⋮ Exact Bounds for the Stochastic Upward Matching Problem ⋮ Bin Packing with Queues ⋮ Multidimensional on-line bin-packing: An algorithm and its average-case analysis ⋮ Adaptive Bin Packing with Overflow
Cites Work
- Unnamed Item
- On optimal matchings
- A lower bound for on-line bin packing
- Probabilistic analysis for simple one- and two-dimensional bin packing algorithms
- Bin packing can be solved within 1+epsilon in linear time
- Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
- Wafer-Scale Integration of Systolic Arrays
- A stochastic model of bin-packing
- Empirical and Poisson processes on classes of sets or functions too large for central limit theorems
- Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
