Polynomiality for Bin Packing with a Constant Number of Item Types

DOI10.1145/3421750MaRDI QIDQ5056451zbMATH OpenOpenAlexWikidataFDO

Authors Michel X. Goemans, Thomas Rothvoß

Publication date 8 December 2022

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3421750

zbMATH Keywords

integer programmingbin packingpolynomial-time algorithmshigh multiplicity scheduling

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Recommendations

• Polynomiality for bin packing with a constant number of item types
• An asymptotically exact algorithm for the high-multiplicity bin packing problem
• Bin packing with fixed number of bins revisited
• A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths
• Bin packing with fixed number of bins revisited

Cited in

(8)

• Bin packing with restricted piece sizes
• Bin packing with fixed number of bins revisited
• Polynomiality for bin packing with a constant number of item types
• About the structure of the integer cone and its application to bin packing
• Parameterized complexity of envy-free resource allocation in social networks
• Serial batching to minimize the weighted number of tardy jobs
• Empowering the configuration-IP: new PTAS results for scheduling with setup times
• Bin packing with fixed number of bins revisited

This page was built for publication: Polynomiality for Bin Packing with a Constant Number of Item Types

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5056451)