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

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
Reinforcement Schedules01:24

Reinforcement Schedules

264
Positive reinforcement is a powerful method for teaching new behaviors to both animals and humans. B.F. Skinner demonstrated this with his experiments using rats in a Skinner box. When a rat pressed a lever, it received a food pellet. This immediate reward encouraged the rat to repeat the behavior. This method, where a reward follows every instance of the behavior, is known as continuous reinforcement. It is highly effective for establishing new behaviors quickly.
Once a behavior is learned,...
264
Group Design02:01

Group Design

9.8K
The most basic experimental design involves two groups: the experimental group and the control group. The two groups are designed to be the same except for one difference— experimental manipulation. The experimental group gets the experimental manipulation—that is, the treatment or variable being tested—and the control group does not. Since experimental manipulation is the only difference between the experimental and control groups, we can be sure that any differences between...
9.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
Random Sampling Method01:09

Random Sampling Method

12.9K
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.9K
Wald-Wolfowitz Runs Test I01:17

Wald-Wolfowitz Runs Test I

758
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...
758

You might also read

Related Articles

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

Sort by
Same author

Best Fit Bin Packing with Random Order Revisited.

Algorithmica·2021
Same author

Improved Online Algorithms for Knapsack and GAP 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 14, 2025

Automated, Quantitative Cognitive/Behavioral Screening of Mice: For Genetics, Pharmacology, Animal Cognition and Undergraduate Instruction
16:23

Automated, Quantitative Cognitive/Behavioral Screening of Mice: For Genetics, Pharmacology, Animal Cognition and Undergraduate Instruction

Published on: February 26, 2014

14.5K

Scheduling in the Random-Order Model.

Susanne Albers1, Maximilian Janke1

  • 1Lehrstuhl für Algorithmen und Komplexität, Institut für Informatik, Technische Universität München, Boltzmannstr. 3, 85748 Garching, Germany.

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

This study introduces a new deterministic online algorithm for makespan minimization in the random-order model, achieving a competitive ratio of 1.8478. This improves upon existing algorithms and provides new lower bounds for this scheduling problem.

Keywords:
Competitive analysisLower boundMakespan minimizationOnline algorithmRandom-orderScheduling

More Related Videos

RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans
11:09

RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans

Published on: July 17, 2021

3.1K
Three Laboratory Procedures for Assessing Different Manifestations of Impulsivity in Rats
09:12

Three Laboratory Procedures for Assessing Different Manifestations of Impulsivity in Rats

Published on: March 17, 2019

9.6K

Related Experiment Videos

Last Updated: Oct 14, 2025

Automated, Quantitative Cognitive/Behavioral Screening of Mice: For Genetics, Pharmacology, Animal Cognition and Undergraduate Instruction
16:23

Automated, Quantitative Cognitive/Behavioral Screening of Mice: For Genetics, Pharmacology, Animal Cognition and Undergraduate Instruction

Published on: February 26, 2014

14.5K
RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans
11:09

RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans

Published on: July 17, 2021

3.1K
Three Laboratory Procedures for Assessing Different Manifestations of Impulsivity in Rats
09:12

Three Laboratory Procedures for Assessing Different Manifestations of Impulsivity in Rats

Published on: March 17, 2019

9.6K

Area of Science:

  • Computer Science
  • Operations Research
  • Algorithm Analysis

Background:

  • Online scheduling problems, specifically makespan minimization on identical parallel machines, are fundamental.
  • The Greedy algorithm has a known competitive ratio, but improved deterministic algorithms are sought.
  • The random-order model, where jobs arrive as a random permutation, presents unique challenges for online algorithms.

Purpose of the Study:

  • To develop a deterministic online algorithm with improved performance guarantees for makespan minimization in the random-order model.
  • To establish new theoretical bounds for online makespan minimization in this specific setting.
  • To provide a rigorous analysis of the proposed algorithm's competitiveness.

Main Methods:

  • A novel deterministic online algorithm is developed.
  • A new analysis approach is employed, identifying properties satisfied by random permutations with high probability.
  • Worst-case analysis is conducted on the algorithm for specific classes of permutations.

Main Results:

  • The proposed algorithm achieves a competitive ratio of 1.8478, the first improvement in this setting.
  • The competitiveness holds with high probability, not just in expectation.
  • New lower bounds are established: 4/3 for any deterministic online algorithm and 3/2 with high probability.

Conclusions:

  • The developed algorithm offers superior performance for online makespan minimization in the random-order model.
  • The analysis demonstrates that pathological inputs leading to poor performance ratios are rare.
  • The new lower bounds provide a tighter theoretical understanding of the problem's complexity.