chapter

Approximation algorithms for bin packing: a survey

Authors:

E. G. Coffman, Jr.,

M. R. Garey,

D. S. JohnsonAuthors Info & Claims

Approximation algorithms for NP-hard problems

August 1996

Pages 46 - 93

Published: 01 August 1996 Publication History

Abstract

No abstract available.

Cited By

View all

Guo ZLi JRamesh R(2023)Green Data Analytics of Supercomputing from Massive Sensor NetworksInformation Systems Research10.1287/isre.2023.120834:4(1664-1685)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1287/isre.2023.1208
Mc Donnell NDuggan JHowley E(2023)A Genetic Programming-based Framework for Semi-automated Multi-agent Systems EngineeringACM Transactions on Autonomous and Adaptive Systems10.1145/358473118:2(1-30)Online publication date: 28-May-2023
https://dl.acm.org/doi/10.1145/3584731
Lichen JLi JLih KYu X(2022)Approximation algorithms for constructing required subgraphs using stock pieces of fixed lengthJournal of Combinatorial Optimization10.1007/s10878-020-00543-x44:3(1774-1795)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s10878-020-00543-x
Show More Cited By

Index Terms

Approximation algorithms for bin packing: a survey
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Design and analysis of algorithms

Recommendations

Approximation algorithms for orthogonal packing problems for hypercubes

Orthogonal packing problems are natural multidimensional generalizations of the classical bin packing problem and knapsack problem and occur in many different settings. The input consists of a set I={r"1,...,r"n} of d-dimensional rectangular items r"i=(...
An improved approximation scheme for variable-sized bin packing
MFCS'12: Proceedings of the 37th international conference on Mathematical Foundations of Computer Science

The variable-sized bin packing problem (VBP) is a well-known generalization of the NP-hard bin packing problem (BP) where the items can be packed in bins of M given sizes. The objective is to minimize the total capacity of the bins used. We present an ...
An Improved Approximation Scheme for Variable-Sized Bin Packing

The Variable-Sized Bin Packing Problem (abbreviated as VSBPP or VBP) is a well-known generalization of the NP-hard Bin Packing Problem (BP) where the items can be packed in bins of M given sizes. The objective is to minimize the total capacity of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Approximation algorithms for NP-hard problems

August 1996

612 pages

ISBN:0534949681

Editor:
Dorit S. Hochbaum
Univ. of California, Berkeley

Publisher

PWS Publishing Co.

United States

Publication History

Published: 01 August 1996

Qualifiers

Chapter

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

212
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Guo ZLi JRamesh R(2023)Green Data Analytics of Supercomputing from Massive Sensor NetworksInformation Systems Research10.1287/isre.2023.120834:4(1664-1685)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1287/isre.2023.1208
Mc Donnell NDuggan JHowley E(2023)A Genetic Programming-based Framework for Semi-automated Multi-agent Systems EngineeringACM Transactions on Autonomous and Adaptive Systems10.1145/358473118:2(1-30)Online publication date: 28-May-2023
https://dl.acm.org/doi/10.1145/3584731
Lichen JLi JLih KYu X(2022)Approximation algorithms for constructing required subgraphs using stock pieces of fixed lengthJournal of Combinatorial Optimization10.1007/s10878-020-00543-x44:3(1774-1795)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s10878-020-00543-x
Epstein LMualem L(2022)Online Bin Packing of Squares and CubesAlgorithmica10.1007/s00453-022-01078-985:5(1415-1458)Online publication date: 12-Dec-2022
https://dl.acm.org/doi/10.1007/s00453-022-01078-9
Valdivia PBuono PPlaisant CDufournaud NFekete J(2021)Analyzing Dynamic Hypergraphs with Parallel Aggregated Ordered Hypergraph VisualizationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2019.293319627:1(1-13)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1109/TVCG.2019.2933196
Psychasand KGhaderi J(2021)High-Throughput Bin Packing: Scheduling Jobs With Random Resource Demands in ClustersIEEE/ACM Transactions on Networking10.1109/TNET.2020.303402229:1(220-233)Online publication date: 16-Feb-2021
https://dl.acm.org/doi/10.1109/TNET.2020.3034022
Epstein LMualem L(2021)Online Bin Packing of Squares and CubesAlgorithms and Data Structures10.1007/978-3-030-83508-8_26(357-370)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-83508-8_26
Xiao TSikdar SEl Fallah Seghrouchni ASukthankar GAn BYorke-Smith N(2020)Size-Relaxed Committee Selection under the Chamberlin-Courant RuleProceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3398761.3398937(1530-1538)Online publication date: 5-May-2020
https://dl.acm.org/doi/10.5555/3398761.3398937
Fan JWang GThürer M(2020)Approximation Algorithms for a New Truck Loading Problem in Urban Freight TransportationTransportation Science10.1287/trsc.2019.096754:3(690-702)Online publication date: 7-May-2020
https://dl.acm.org/doi/10.1287/trsc.2019.0967
Ilin IKubarskii ASchuur PLepekhin ADubgorn A(2020)Cloud Application For Sheet Materials Cutting OptimizationProceedings of the International Scientific Conference - Digital Transformation on Manufacturing, Infrastructure and Service10.1145/3446434.3446469(1-5)Online publication date: 18-Nov-2020
https://dl.acm.org/doi/10.1145/3446434.3446469
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

Approximation algorithms for orthogonal packing problems for hypercubes

An improved approximation scheme for variable-sized bin packing

An Improved Approximation Scheme for Variable-Sized Bin Packing

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations