The robustness of the sum-of-squares algorithm for bin packing

Michael A. Bender; Bryan Bradley; Geetha Jagannathan; Krishnan Pillaipakkamnatt

The robustness of the sum-of-squares algorithm for bin packing

Michael A. Bender
, Bryan Bradley
, Geetha Jagannathan
, Krishnan Pillaipakkamnatt

Computer Science

Hofstra University
Stony Brook University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Three sets of results that demonstrate the robustness of the sum-of-squares (SS) algorithm were presented. The results of experiments from two variants, one which runs in time O(√B log B) and the other which runs in O(n log B), were also presented. The results from experiments that extend the SS algorithm to the bin-packing problem with two bin sizes were also presented. The application of the SS algorithm to the related problem of online memory allocation was elaborated.

Original language	English
Title of host publication	Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics
Editors	L. Arge, G.F. Italiano, R. Sedgewick
Pages	18-30
Number of pages	13
State	Published - 2004
Event	Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics - New Orleans, LA, United States Duration: Jan 10 2004 → Jan 10 2004

Publication series

Name	Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics

Conference

Conference	Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics
Country/Territory	United States
City	New Orleans, LA
Period	01/10/04 → 01/10/04

Cite this

Bender, M. A., Bradley, B., Jagannathan, G., & Pillaipakkamnatt, K. (2004). The robustness of the sum-of-squares algorithm for bin packing. In L. Arge, G. F. Italiano, & R. Sedgewick (Eds.), Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics (pp. 18-30). (Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics).

Bender, Michael A. ; Bradley, Bryan ; Jagannathan, Geetha et al. / The robustness of the sum-of-squares algorithm for bin packing. Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics. editor / L. Arge ; G.F. Italiano ; R. Sedgewick. 2004. pp. 18-30 (Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics).

@inproceedings{d956c125f80c4afd93b89a4b3fcbd421,

title = "The robustness of the sum-of-squares algorithm for bin packing",

abstract = "Three sets of results that demonstrate the robustness of the sum-of-squares (SS) algorithm were presented. The results of experiments from two variants, one which runs in time O(√B log B) and the other which runs in O(n log B), were also presented. The results from experiments that extend the SS algorithm to the bin-packing problem with two bin sizes were also presented. The application of the SS algorithm to the related problem of online memory allocation was elaborated.",

author = "Bender, \{Michael A.\} and Bryan Bradley and Geetha Jagannathan and Krishnan Pillaipakkamnatt",

year = "2004",

language = "English",

isbn = "0898715644",

series = "Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics",

pages = "18--30",

editor = "L. Arge and G.F. Italiano and R. Sedgewick",

booktitle = "Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics",

note = "Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics ; Conference date: 10-01-2004 Through 10-01-2004",

}

Bender, MA, Bradley, B, Jagannathan, G & Pillaipakkamnatt, K 2004, The robustness of the sum-of-squares algorithm for bin packing. in L Arge, GF Italiano & R Sedgewick (eds), Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics. Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics, pp. 18-30, Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics, New Orleans, LA, United States, 01/10/04.

The robustness of the sum-of-squares algorithm for bin packing. / Bender, Michael A.; Bradley, Bryan; Jagannathan, Geetha et al.
Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics. ed. / L. Arge; G.F. Italiano; R. Sedgewick. 2004. p. 18-30 (Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - The robustness of the sum-of-squares algorithm for bin packing

AU - Bender, Michael A.

AU - Bradley, Bryan

AU - Jagannathan, Geetha

AU - Pillaipakkamnatt, Krishnan

PY - 2004

Y1 - 2004

N2 - Three sets of results that demonstrate the robustness of the sum-of-squares (SS) algorithm were presented. The results of experiments from two variants, one which runs in time O(√B log B) and the other which runs in O(n log B), were also presented. The results from experiments that extend the SS algorithm to the bin-packing problem with two bin sizes were also presented. The application of the SS algorithm to the related problem of online memory allocation was elaborated.

AB - Three sets of results that demonstrate the robustness of the sum-of-squares (SS) algorithm were presented. The results of experiments from two variants, one which runs in time O(√B log B) and the other which runs in O(n log B), were also presented. The results from experiments that extend the SS algorithm to the bin-packing problem with two bin sizes were also presented. The application of the SS algorithm to the related problem of online memory allocation was elaborated.

UR - https://www.scopus.com/pages/publications/8344280351

M3 - Conference contribution

AN - SCOPUS:8344280351

SN - 0898715644

T3 - Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics

SP - 18

EP - 30

BT - Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics

A2 - Arge, L.

A2 - Italiano, G.F.

A2 - Sedgewick, R.

T2 - Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics

Y2 - 10 January 2004 through 10 January 2004

ER -

Bender MA, Bradley B, Jagannathan G, Pillaipakkamnatt K. The robustness of the sum-of-squares algorithm for bin packing. In Arge L, Italiano GF, Sedgewick R, editors, Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics. 2004. p. 18-30. (Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics).

The robustness of the sum-of-squares algorithm for bin packing

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this