AFPTAS results for common variants of bin packing: a new method for handling the small items

DOI10.1137/090767613zbMATH Open1211.68510arXiv0906.5050OpenAlexW2053900376MaRDI QIDQ3083324FDOQ3083324

Leah Epstein, Asaf Levin

Publication date: 21 March 2011

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: We consider two well-known natural variants of bin packing, and show that these packing problems admit asymptotic fully polynomial time approximation schemes (AFPTAS). In bin packing problems, a set of one-dimensional items of size at most 1 is to be assigned (packed) to subsets of sum at most 1 (bins). It has been known for a while that the most basic problem admits an AFPTAS. In this paper, we develop methods that allow to extend this result to other variants of bin packing. Specifically, the problems which we study in this paper, for which we design asymptotic fully polynomial time approximation schemes, are the following. The first problem is "Bin packing with cardinality constraints", where a parameter k is given, such that a bin may contain up to k items. The goal is to minimize the number of bins used. The second problem is "Bin packing with rejection", where every item has a rejection penalty associated with it. An item needs to be either packed to a bin or rejected, and the goal is to minimize the number of used bins plus the total rejection penalty of unpacked items. This resolves the complexity of two important variants of the bin packing problem. Our approximation schemes use a novel method for packing the small items. This new method is the core of the improved running times of our schemes over the running times of the previous results, which are only asymptotic polynomial time approximation schemes (APTAS).

Full work available at URL: https://arxiv.org/abs/0906.5050

Recommendations

• A fast asymptotic approximation scheme for bin packing with rejection
• A Fast Asymptotic Approximation Scheme for Bin Packing with Rejection
• An improved approximation scheme for variable-sized bin packing
• Bin Packing with Rejection Revisited
• An improved approximation scheme for variable-sized bin packing

zbMATH Keywords

approximation algorithmbin packingworst case analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cited In (27)

• Title not available (Why is that?)
• Approximation schemes for packing splittable items with cardinality constraints
• Improved results for a memory allocation problem
• Several methods of analysis for cardinality constrained bin packing
• Several methods of analysis for cardinality constrained bin packing
• Scheduling with cardinality dependent unavailability periods
• Selfish bin packing with cardinality constraints
• EPTAS for the dual of splittable bin packing with cardinality constraint
• Bin packing with general cost structures
• Combinatorial algorithms for solving the constrained knapsack problems with divisible item sizes and penalties
• On the generalized bin packing problem
• Title not available (Why is that?)
• The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints
• Bin packing with controllable item sizes
• Offline black and white bin packing
• Bin covering with cardinality constraints
• Bin packing with divisible item sizes and rejection penalties
• Robust algorithms for preemptive scheduling
• Online bin packing with cardinality constraints resolved
• An AFPTAS for variable sized bin packing with general activation costs
• Approximation Schemes for Machine Scheduling with Resource (In-)dependent Processing Times
• Bin packing with rejection revisited
• Improved lower bounds for the online bin packing problem with cardinality constraints
• A Fast Asymptotic Approximation Scheme for Bin Packing with Rejection
• Class constrained bin packing revisited
• Set Covering with Ordered Replacement: Additive and Multiplicative Gaps
• Bounds for online bin packing with cardinality constraints

This page was built for publication: AFPTAS results for common variants of bin packing: a new method for handling the small items

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