Back to search

Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics

Data up to Jan 2025

Published1988
Citations63
References58

Total Citations Per Year

Abstract

References (58)

Computers and Intractability: A Guide to the Theory of NP-Completeness

1979 • 45,565 citations

An introduction to probability theory and its applications

1958 • 31,109 citations

Probability Inequalities for sums of Bounded Random Variables

1994 • 7,059 citations

Approximation Theorems of Mathematical Statistics

1980 • 5,851 citations

A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

1952 • 3,575 citations

A second course in stochastic processes

1981 • 2,967 citations

Complexity of Computer Computations

1972 • 2,804 citations

Reducibility Among Combinatorial Problems

2009 • 2,333 citations

Bounds on Multiprocessing Timing Anomalies

1969 • 2,307 citations

Almost Sure Convergence.

1975 • 1,313 citations

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

1974 • 910 citations

Probabilistic Methods in Combinatorics

1974 • 616 citations

Big Omicron and big Omega and big Theta

1976 • 591 citations

Near-optimal bin packing algorithms

1973 • 574 citations

Approximation Algorithms for Bin-Packing — An Updated Survey

1984 • 418 citations

Distribution Theory for Tests Based on the Sample Distribution Function.

1974 • 381 citations

On optimal matchings

1984 • 244 citations

The Differencing Method of Set Partitioning

1983 • 207 citations

Covering the circle with random ARCS

1972 • 147 citations

The average-case analysis of some on-line algorithms for bin packing

1986 • 101 citations

A stochastic model of bin-packing

1980 • 99 citations

Martingale Inequalities and NP-Complete Problems

1987 • 91 citations

Covering the line with random intervals

1972 • 88 citations

A probabilistic analysis of multidimensional bin packing problems

1984 • 84 citations

Experimental Analysis of Algorithms

2002 • 77 citations

Some unexpected expected behavior results for bin packing

1984 • 68 citations

Bin packing with items uniformly distributed over intervals [a,b]

1983 • 60 citations

Tight bounds for minimax grid matching, with applications to the average case analysis of algorithms

1986 • 58 citations

Probabilistic analysis of optimum partitioning

1986 • 55 citations

Probabilistic analysis for simple one-and two-dimensional bin packing algorithms

1980 • 50 citations

Optimal Bin Packing with Items of Random Sizes

1988 • 46 citations

Probabilistic Analysis of Bin Packing Heuristics

1984 • 42 citations

Two-dimensional packing: expected performance of simple level algorithms

1980 • 38 citations

A bin packing algorithm with complexity O(n log n) and performance 1 in the stochastic limit

1981 • 38 citations

Probabilistic analysis of some bin-packing problems

1982 • 38 citations

Probabilistic bounds for dual bin-packing

1985 • 36 citations

An average-case analysis of bin packing with uniformly distributed item sizes

1982 • 35 citations

On the Expected Relative Performance of List Scheduling

1985 • 34 citations

A provably efficient algorithm for dynamic storage allocation

1986 • 34 citations

Séries de Fourier aléatoirement bornées, continues, uniformément convergentes

1965 • 33 citations

A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors

1984 • 30 citations

Optimal Bin Packing with Items of Random Sizes III

1989 • 29 citations

Tight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor Scheduling

1984 • 26 citations

Probabilistic Bounds on the Performance of List Scheduling

1986 • 24 citations

A probabilistic analysis of the Next-Fit bin packing algorithm

1984 • 23 citations

A probabilistic analysis of the next fit decreasing bin packing heuristic

1986 • 21 citations

On the rate of convergence to optimality of the LPT rule

2011 • 19 citations

Some distributions that allow perfect packing

1988 • 15 citations

A stochastic analysis of the NFD bin-packing algorithm

1986 • 14 citations

A note on the average-case behavior of a simple differencing method for partitioning

1987 • 12 citations

A Probabilistic Analysis of the LPT Scheduling Rule

1984 • 11 citations

Expected Makespans for Largest-First Multiprocessor Scheduling

1984 • 10 citations

Probabilistic behaviour of optical bin-packing solutions

1984 • 10 citations

FFD bin packing for item sizes with distributions on [0,1/2]

1986 • 6 citations

A probabilistic analysis of multiprocessor list scheduling: the erlang case

1985 • 4 citations

A probabilistic analysis of the dual bin packing problem

1986 • 2 citations

On the monotonicity of certain bin packing algorithms

1984 • 1 citations

Deleted Work

1955 • 0 citations

Cited By (0)

Loading...