Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Binomial Probability Distribution01:15

Binomial Probability Distribution

13.0K
A binomial distribution is a probability distribution for a procedure with a fixed number of trials, where each trial can have only two outcomes.
The outcomes of a binomial experiment fit a binomial probability distribution. A statistical experiment can be classified as a binomial experiment if the following conditions are met:
There are a fixed number of trials. Think of trials as repetitions of an experiment. The letter n denotes the number of trials.
There are only two possible outcomes,...
13.0K
Law of Independent Assortment02:03

Law of Independent Assortment

58.0K
While Mendel’s Law of Segregation states that the two alleles for one gene are separated into different gametes, a different question of how different genes are inherited remains. For example, is the gene for tall plants inherited with the gene for green peas? Mendel asked this question by experimenting with a dihybrid cross; a cross in which both parents are homozygous for two distinct traits resulting in an F1 generation that are heterozygous for both traits.
58.0K
Randomized Experiments01:13

Randomized Experiments

8.2K
The randomization process involves assigning study participants randomly to experimental or control groups based on their probability of being equally assigned. Randomization is meant to eliminate selection bias and balance known and unknown confounding factors so that the control group is similar to the treatment group as much as possible. A computer program and a random number generator can be used to assign participants to groups in a way that minimizes bias.
Simple randomization
Simple...
8.2K
Wald-Wolfowitz Runs Test I01:17

Wald-Wolfowitz Runs Test I

756
The Wald-Wolfowitz test, also known as the runs test, is a nonparametric statistical test used to assess the randomness of a sequence of two different types of elements (e.g., positive/negative values, successes/failures). It examines whether the order of the elements in a sequence is random or if there is a pattern or trend present. This nonparametric test applies to any ordered data despite the population and sample data distribution, even if a higher sample size is available.
The test works...
756
Random Sampling Method01:09

Random Sampling Method

12.8K
Sampling is a technique to select a portion (or subset) of the larger population and study that portion (the sample) to gain information about the population. Data are the result of sampling from a population. The sampling method ensures that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest. Among the various sampling methods used by...
12.8K
Random Variables01:09

Random Variables

15.1K
A random variable is a single numerical value that indicates the outcome of a procedure. The concept of random variables is fundamental to the probability theory and was introduced by a Russian mathematician, Pafnuty Chebyshev, in the mid-nineteenth century.
Uppercase letters such as X or Y denote a random variable. Lowercase letters like x or y denote the value of a random variable. If X is a random variable, then X is written in words, and x is given as a number.
For example, let X = the...
15.1K

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Improved Online Algorithms for Knapsack and GAP in the Random Order Model.

Algorithmica·2021
Same author

Scheduling in the Random-Order Model.

Algorithmica·2021
Same author

Motivating Time-Inconsistent Agents: A Computational Approach.

Theory of computing systems·2019
Same journal

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity.

Algorithmica·2026
Same journal

A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games.

Algorithmica·2026
Same journal

Fully Characterizing Lossy Catalytic Computation.

Algorithmica·2026
Same journal

Parameterized Complexities of Dominating and Independent Set Reconfiguration.

Algorithmica·2026
Same journal

The SLO Hierarchy of Pseudo-Boolean Functions and Runtime of Evolutionary Algorithms.

Algorithmica·2026
Same journal

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem.

Algorithmica·2025
See all related articles

Related Experiment Video

Updated: Oct 13, 2025

Design and Optimization Strategies of a High-Performance Vented Box
14:23

Design and Optimization Strategies of a High-Performance Vented Box

Published on: June 9, 2023

1.3K

Best Fit Bin Packing with Random Order Revisited.

Susanne Albers1, Arindam Khan2, Leon Ladewig1

  • 1Department of Computer Science, Technial University of Munich, Boltzmannstr. 3, 85748 Garching, Germany.

Algorithmica
|November 15, 2021
PubMed
Summary
This summary is machine-generated.

This study improves the analysis of the Best Fit algorithm for bin packing. Researchers established a new lower bound for its random order ratio, enhancing understanding of its performance with large items.

Keywords:
Online bin packingProbabilistic analysisRandom arrival order

More Related Videos

Selecting Multiple Biomarker Subsets with Similarly Effective Binary Classification Performances
07:35

Selecting Multiple Biomarker Subsets with Similarly Effective Binary Classification Performances

Published on: October 11, 2018

7.7K
Barnes Maze Testing Strategies with Small and Large Rodent Models
12:59

Barnes Maze Testing Strategies with Small and Large Rodent Models

Published on: February 26, 2014

42.6K

Related Experiment Videos

Last Updated: Oct 13, 2025

Design and Optimization Strategies of a High-Performance Vented Box
14:23

Design and Optimization Strategies of a High-Performance Vented Box

Published on: June 9, 2023

1.3K
Selecting Multiple Biomarker Subsets with Similarly Effective Binary Classification Performances
07:35

Selecting Multiple Biomarker Subsets with Similarly Effective Binary Classification Performances

Published on: October 11, 2018

7.7K
Barnes Maze Testing Strategies with Small and Large Rodent Models
12:59

Barnes Maze Testing Strategies with Small and Large Rodent Models

Published on: February 26, 2014

42.6K

Area of Science:

  • Computer Science
  • Operations Research
  • Algorithm Analysis

Background:

  • The bin packing problem is a classic optimization challenge.
  • Online algorithms process input sequentially without future knowledge.
  • Best Fit is a well-known online algorithm for bin packing.
  • The random order ratio analyzes algorithm performance when item arrival order is randomized.

Purpose of the Study:

  • To improve the theoretical performance bounds for the Best Fit algorithm in the context of the random order ratio.
  • To investigate the impact of item sizes on Best Fit's performance.
  • To introduce and analyze the absolute random order ratio for online bin packing.

Main Methods:

  • Theoretical analysis of the Best Fit algorithm.
  • Development of new lower and upper bounds for the random order ratio.
  • Examination of specific cases, such as instances with items larger than 1/3.
  • Introduction of the absolute random order ratio as a performance metric.

Main Results:

  • An improved lower bound of 1.10 for the asymptotic random order ratio of Best Fit was established, narrowing the gap from Kenyon's 1996 result.
  • For instances where all items are larger than 1/3, the random order ratio converges to 1.25.
  • Best Fit exhibits a monotonicity property for instances with large items, unlike in the general case.
  • The absolute random order ratio for Best Fit was shown to be at least 1.3.
  • For large items, specific bounds of 21/16 and 1.2 were derived for the absolute random order ratio.

Conclusions:

  • The performance analysis of Best Fit is significantly advanced by the new bounds, particularly highlighting the role of large items.
  • The study provides a more refined understanding of Best Fit's efficiency in online settings.
  • The introduction of the absolute random order ratio offers a new perspective for evaluating online algorithms under stricter conditions.