Bounded Space On-Line Bin Packing: Best Is Better than First

No abstract is available for this paper.

• Publication year

  1991

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  1991-03-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00453-001-0041-7
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Tight Worst-Case Performance Bounds for Next-k-Fit Bin Packing

  1993cited by this paper
• Improved Space for Bounded-Space, On-Line Bin-Packing

  1993influential reference
• An Improved Lower Bound for On-Line Bin Packing Algorithms

  1992cited by this paper
• Improved bounds for harmonic-based bin packing algorithms

  1991influential reference
• Average-Case Analysis of the Smart Next Fit Algorithm

  1989cited by this paper
• On the worst-case performance of the NkF bin-packing heuristic

  1989cited by this paper
• On-Line Bin Packing in Linear Time

  1989influential reference
• A probabilistic analysis of the next fit decreasing bin packing heuristic

  1986cited by this paper
• A probabilistic analysis of the next fit decreasing bin packing heuristic

  1986cited by this paper
• Some unexpected expected behavior results for bin packing

  1984cited by this paper
• The average-case analysis of some on-line algorithms for bin packing

  1984influential reference
• An average-case analysis of bin packing with uniformly distributed item sizes

  1982cited by this paper
• A Bin Packing Algorithm with Complexity O(n log n) and Performance 1 in the Stochastic Limit

  1981cited by this paper
• Probabilistic Analysis for Simple One- and Two-Dimensional Bin Packing Algorithms

  1980cited by this paper
• A Stochastic Model of Bin-Packing

  1980influential reference
• A Lower Bound for On-Line Bin Packing

  1980influential reference
• A Lower Bound for On-Line One-Dimensional Bin Packing Algorithms.

  1979cited by this paper
• Resource Constrained Scheduling as Generalized Bin Packing

  1976cited by this paper
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

  1974cited by this paper
• Fast Algorithms for Bin Packing

  1974cited by this paper
• Near-optimal bin packing algorithms

  1973influential reference
• The Art of Computer Programming, Volume II: Seminumerical Algorithms

  1970cited by this paper

• Lower Bounds for Several Standard Bin Packing Algorithms in the Random Order Model

  2025cites this paper
• A Decision Support Tool for Aggregation and Prioritisation of Energy Efficiency Investments in Buildings

  2024cites this paper
• Tighter bounds for the harmonic bin packing algorithm

  2024cites this paper
• Exact reoptimisation under gradual look-ahead for operational control in production and logistics

  2022cites this paper
• Deep reinforcement learning in POMDPs for 3-D palletization problem

  2022cites this paper
• On-line three-dimensional packing problems: A review of off-line and on-line solution approaches

  2022cites this paper
• Homogeneous grouping of non-prime steel products for online auctions: a case study

  2022cites this paper
• Efficient and scalable multitenant placement approach for in-memory database over supple architecture

  2020cites this paper
• An Automatic Algorithm Configuration based on a Bayesian Network

  2020cites this paper
• A structuring review on multi-stage optimization under uncertainty: Aligning concepts from theory and practice

  2020cites this paper
• A data-driven methodology for the automated configuration of online algorithms

  2020cites this paper
• Improvement Grouping Genetic Algorithm for Solving the Bin Packing Problem

  2020cites this paper
• Efficient 1-Space Bounded Hypercube Packing Algorithm

  2020cites this paper
• Robot Packing With Known Items and Nondeterministic Arrival Order

  2019cites this paper
• New Results on the Probabilistic Analysis of Online Bin Packing and its Variants

  2019cites this paper
• A Tale of Two Packing Problems: Improved Algorithms and Tighter Bounds for Online Bin Packing and the Geometric Knapsack Problem

  2018cites this paper
• Colored Bin Packing: Online Algorithms and Lower Bounds

  2016cites this paper
• Harmonic Algorithm for Online Bin Packing

  2016cites this paper
• Improved Online Algorithms for 2-Space Bounded 2-Dimensional Bin Packing

  2016cites this paper
• A note on one-space bounded square packing

  2015cites this paper
• Harmonic Algorithm for Bin Packing.

  2015cites this paper
• Locality-preserving allocations problems and coloured bin packing

  2015influential citation
• Online Bin Packing: Old Algorithms and New Results

  2014influential citation
• Efficient Online Strategies for Renting Servers in the Cloud

  2014cites this paper
• Algorithms for RTP

  2014cites this paper
• Online Colored Bin Packing

  2014cites this paper
• Title Online algorithms for 1-space bounded multi dimensional binpacking and hypercube packing

  2013influential citation
• Bin packing approximation algorithms: Survey and classification

  2013cites this paper
• Online algorithms for 1-space bounded 2-dimensional bin packing and square packing

  2013cites this paper
• Online algorithms for 1-space bounded multi dimensional bin packing and hypercube packing

  2013influential citation
• RTP: robust tenant placement for elastic in-memory database clusters

  2013cites this paper
• Generic Algorithm Implementation of Approximation Algorithm using Simulated Annealing (SA)

  2013cites this paper
• On-line algorithms for 2-space bounded 2-dimensional bin packing

  2012cites this paper
• A New Analysis of Best Fit Bin Packing

  2012influential citation
• Online Algorithms in Resource Management and Constraint Satisfaction

  2012cites this paper
• SIGACT news online algorithms column 20: the power of harmony

  2012cites this paper
• Algorithms for energy-driven agent placement in wireless embedded systems with memory constraints

  2011cites this paper
• Probabilistic alternatives for competitive analysis

  2011cites this paper
• Improving the 1-Bounded Space Algorithms for 2-Dimensional Online Bin Packing

  2011cites this paper
• Two-Bounded-Space Bin Packing Revisited

  2011cites this paper
• Online Algorithm for 1-Space Bounded Multi-dimensional Bin Packing

  2011influential citation
• A deterministic harvest scheduler using perfect bin-packing theorem

  2010influential citation
• One-Space Bounded Algorithms for Two-Dimensional Bin Packing

  2010cites this paper
• Improved Online Algorithms for 1-Space Bounded 2-Dimensional Bin Packing

  2010influential citation
• Online Optimization: Probabilistic Analysis and Algorithm Engineering

  2010cites this paper
• 1-Bounded Space Algorithms for 2-Dimensional Bin Packing

  2009influential citation
• Looking-Ahead Algorithms for Single Machine Schedulers to Support Advance Reservation of Grid Jobs

  2008influential citation
• An On-Line Access Selection Algorithm for ABC Networks Supporting Elastic Services

  2008cites this paper
• An On-line Scheduling Heuristic with Better Worst Case Ratio than Graham's List Scheduling. Siam

  2007cites this paper
• Online Algorithms for Single Machine Schedulers to Support Advance Reservations from Grid Jobs

  2007cites this paper
• An Evaluation of Bin-Packing Algorithms Using Real Program Traces

  2007cites this paper
• Average Case Analysis of Bounded Space Bin Packing Algorithms

  2007influential citation
• Analysis of Access Selection Algorithms for Multi-access Networks with Elastic Traffic ∗

  2006influential citation
• Improved Approximation Algorithms for Maximum Resource Bin Packing and Lazy Bin Covering Problems

  2006cites this paper
• Computations with Exact Numbers

  2006cites this paper
• Adversarial Reasoning: Computational Approaches to Reading the Opponent's Mind

  2006influential citation
• On Lazy Bin Covering and Packing problems

  2006cites this paper
• Simulative analysis of access selection algorithms for multi-access networks

  2006influential citation
• Asymptotic Worst-Case Analyses for the Open Bin Packing Problem

  2005influential citation
• On stable embeddability of partitions

  2005cites this paper
• Asymptotic Worst-Case Analyses for the Open Bin Packing Problem

  2005cites this paper
• Improving Restoration Success in Mesh Optical Networks

  2004cites this paper
• Improving restoration success in mesh optical networks [Invited]

  2003cites this paper
• Link selection schemes for avoiding channel contention

  2003cites this paper
• Performance Analysis and Improvement for Some Linear On-Line Bin-Packing Algorithms

  2002cites this paper
• Approximate solutions to bin packing problems

  2002cites this paper
• Deep performance analysis of Refined Harmonic bin packing algorithm

  2002cites this paper
• Algorithms for the Relaxed Online Bin-Packing Model

  2000cites this paper
• Bin Packing Approximation Algorithms: Combinatorial Analysis

  1999cites this paper
• Online and Real-Time Dispatching Problems

  1999cites this paper
• A 17/10-approximation algorithm fork-bounded space on-line variable-sized bin packing

  1998cites this paper
• Tight performance bound ofAFBk bin packing

  1997cites this paper
• Bounded Space On-Line Variable-Sized Bin Packing

  1997influential citation
• On-line Packing and Covering Problems

  1996influential citation
• On the Asymptotic Worst Case Behavior of Harmonic Fit

  1996cites this paper
• On-line bin packing — A restricted survey

  1995cites this paper
• Online bin packing with lookahead

  1995influential citation
• Repacking helps in bounded space on-line bind-packing

  1993cites this paper
• Improved Space for Bounded-Space, On-Line Bin-Packing

  1993cites this paper
• Besk-k-Fit bin packing

  1993cites this paper
• Tight Worst-Case Performance Bounds for Next-k-Fit Bin Packing

  1993cites this paper
• Analyzing algorithms by simulation: variance reduction techniques and simulation speedups

  1992cites this paper
• Fundamental discrepancies between average-case analyses under discrete and continuous distributions: a bin packing case study

  1991cites this paper