Polynomial time approximation schemes for class-constrained packing problems
The paper considers generalizations of the classical bin packing and multiple knapsack problems. It is assumed that every item is given a size and a class (a colour). In the class-constrained bin packing (CCBP) problem it is required to minimize the number of bins of the unit size that can be used to pack all items, provided that a bin contains items of no more than a prescribed number of colours. In the class-constrained multiple-knapsack (CCMK) problem each item additionally is given a value (profit), the total number of bins of various sizes is given and it is required to maximize total value of items placed in the bins, provided that the size constraints and the colour constraints are respected. Problem CCMK is shown to admit a polynomial-time approximation scheme (PTAS) that finds a placement with a value at least \((1-\varepsilon)\) times the optimum. Further, problem CCMK with a single bin admits a fully polynomial-time approximation scheme. For problem CCBP a dual PTAS is developed that allows a placement into the optimal number of bins provided that the bin size is extended to \(1-\varepsilon\). On the other hand, if an item can take any colour of a given set of colours, the resulting generalized packing problem becomes APX-hard even in the case of a single bin, equal sizes and equal values of all items.
- `` Strong NP-Completeness Results
- A heuristic routine for solving large loading problems
- An Algorithm for the Solution of 0-1 Loading Problems
- An approximation algorithm for the generalized assignment problem
- Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems
- Approximate algorithms for some generalized knapsack problems
- Approximation algorithms for knapsack problems with cardinality constraints
- Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
- Bin packing can be solved within 1+epsilon in linear time
- Cardinality constrained bin-packing problems
- Design and implementation of scalable continuous media servers
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1305407 (Why is no real title available?)
- scientific article; zbMATH DE number 544186 (Why is no real title available?)
- scientific article; zbMATH DE number 1405790 (Why is no real title available?)
- scientific article; zbMATH DE number 1445306 (Why is no real title available?)
- scientific article; zbMATH DE number 1445307 (Why is no real title available?)
- scientific article; zbMATH DE number 6472625 (Why is no real title available?)
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Multiresource malleable task scheduling to minimize response time
- On two class-constrained versions of the multiple knapsack problem
- Solving Multiple Knapsack Problems by Cutting Planes
- The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints
- VNS matheuristic for a bin packing problem with a color constraint
- The multiple multidimensional knapsack with family-split penalties
- Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms
- The class constrained bin packing problem with applications to video-on-demand
- A one-dimensional bin packing problem with shelf divisions
- Bounds for online bin packing with cardinality constraints
- The one dimensional Compartmentalised Knapsack problem: a case study
- scientific article; zbMATH DE number 1670546 (Why is no real title available?)
- Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison
- A note on dual approximation algorithms for class constrained bin packing problems
- Selfish bin coloring
- Approximation schemes for generalized two-dimensional vector packing with application to data placement
- The constrained compartmentalized knapsack problem: mathematical models and solution methods
- Bin packing with directed stackability conflicts
- On two class-constrained versions of the multiple knapsack problem
- Tight bounds for online class-constrained packing
- A decomposition approach for multidimensional knapsacks with family‐split penalties
- Minimal cost reconfiguration of data placement in a storage area network
- Approximation schemes for knapsack problems with shelf divisions
- The constrained compartmentalised knapsack problem
- Pseudo-polynomial time algorithms for combinatorial food mixture packing problems
- Class constrained bin covering
- Algorithms for storage allocation based on client preferences
- Class constrained bin packing revisited
This page was built for publication: Polynomial time approximation schemes for class-constrained packing problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1348737)
