Asymptotic optimality of Best-Fit for stochastic bin packing

Javad Ghaderi, Yuan Zhong, R. Srikant

Research output: Contribution to journalConference article

Abstract

In the static bin packing problem, items of different sizes must be packed into bins or servers with unit capacity in a way that minimizes the number of bins used, and it is well-known to be a hard combinatorial problem. Best-Fit is among the simplest online heuristics for this problem. Motivated by the problem of packing virtual machines in servers in the cloud, we consider the dynamic version of this problem, when jobs arrive randomly over time and leave the system after completion of their service. We analyze the fluid limits of the system under an asymptotic Best-Fit algorithm and show that it asymptotically minimizes the number of servers used in steady state (on the fluid scale). The significance of the result is due to the fact that Best-Fit seems to achieve the best performance in practice.

Original languageEnglish (US)
Pages (from-to)64-66
Number of pages3
JournalPerformance Evaluation Review
Volume42
Issue number2
DOIs
StatePublished - Sep 4 2014
Event32nd International Symposium on Computer Performance, Modeling, Measurement, and Evaluation, IFIP WG 7.3 Performance 2014 - Turin, Italy
Duration: Oct 7 2014Oct 9 2014

Fingerprint

Bins
Servers
Fluids

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Asymptotic optimality of Best-Fit for stochastic bin packing. / Ghaderi, Javad; Zhong, Yuan; Srikant, R.

In: Performance Evaluation Review, Vol. 42, No. 2, 04.09.2014, p. 64-66.

Research output: Contribution to journalConference article

Ghaderi, Javad ; Zhong, Yuan ; Srikant, R. / Asymptotic optimality of Best-Fit for stochastic bin packing. In: Performance Evaluation Review. 2014 ; Vol. 42, No. 2. pp. 64-66.
@article{bd594b4807f748cd85e818bcb666f8b9,
title = "Asymptotic optimality of Best-Fit for stochastic bin packing",
abstract = "In the static bin packing problem, items of different sizes must be packed into bins or servers with unit capacity in a way that minimizes the number of bins used, and it is well-known to be a hard combinatorial problem. Best-Fit is among the simplest online heuristics for this problem. Motivated by the problem of packing virtual machines in servers in the cloud, we consider the dynamic version of this problem, when jobs arrive randomly over time and leave the system after completion of their service. We analyze the fluid limits of the system under an asymptotic Best-Fit algorithm and show that it asymptotically minimizes the number of servers used in steady state (on the fluid scale). The significance of the result is due to the fact that Best-Fit seems to achieve the best performance in practice.",
author = "Javad Ghaderi and Yuan Zhong and R. Srikant",
year = "2014",
month = "9",
day = "4",
doi = "10.1145/2667522.2667543",
language = "English (US)",
volume = "42",
pages = "64--66",
journal = "Performance Evaluation Review",
issn = "0163-5999",
publisher = "Association for Computing Machinery (ACM)",
number = "2",

}

TY - JOUR

T1 - Asymptotic optimality of Best-Fit for stochastic bin packing

AU - Ghaderi, Javad

AU - Zhong, Yuan

AU - Srikant, R.

PY - 2014/9/4

Y1 - 2014/9/4

N2 - In the static bin packing problem, items of different sizes must be packed into bins or servers with unit capacity in a way that minimizes the number of bins used, and it is well-known to be a hard combinatorial problem. Best-Fit is among the simplest online heuristics for this problem. Motivated by the problem of packing virtual machines in servers in the cloud, we consider the dynamic version of this problem, when jobs arrive randomly over time and leave the system after completion of their service. We analyze the fluid limits of the system under an asymptotic Best-Fit algorithm and show that it asymptotically minimizes the number of servers used in steady state (on the fluid scale). The significance of the result is due to the fact that Best-Fit seems to achieve the best performance in practice.

AB - In the static bin packing problem, items of different sizes must be packed into bins or servers with unit capacity in a way that minimizes the number of bins used, and it is well-known to be a hard combinatorial problem. Best-Fit is among the simplest online heuristics for this problem. Motivated by the problem of packing virtual machines in servers in the cloud, we consider the dynamic version of this problem, when jobs arrive randomly over time and leave the system after completion of their service. We analyze the fluid limits of the system under an asymptotic Best-Fit algorithm and show that it asymptotically minimizes the number of servers used in steady state (on the fluid scale). The significance of the result is due to the fact that Best-Fit seems to achieve the best performance in practice.

UR - http://www.scopus.com/inward/record.url?scp=84908211302&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84908211302&partnerID=8YFLogxK

U2 - 10.1145/2667522.2667543

DO - 10.1145/2667522.2667543

M3 - Conference article

AN - SCOPUS:84908211302

VL - 42

SP - 64

EP - 66

JO - Performance Evaluation Review

JF - Performance Evaluation Review

SN - 0163-5999

IS - 2

ER -