Polynomial time approximation schemes for class-constrained packing problems

DOI10.1002/jos.86zbMath1028.90048OpenAlexW2166185745MaRDI QIDQ1348737

Tami Tamir, Hadas Shachnai

Publication date: 27 July 2003

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jos.86

zbMATH Keywords

class-constrained bin packingclass-constrained multiple-knapsack

Mathematics Subject Classification ID

Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (23)

Approximation schemes for knapsack problems with shelf divisions ⋮ Bounds for online bin packing with cardinality constraints ⋮ The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints ⋮ Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms ⋮ The one dimensional Compartmentalised Knapsack problem: a case study ⋮ The constrained compartmentalised knapsack problem ⋮ Tight bounds for online class-constrained packing ⋮ VNS matheuristic for a bin packing problem with a color constraint ⋮ 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 ⋮ A decomposition approach for multidimensional knapsacks with family‐split penalties ⋮ Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison ⋮ Minimal cost reconfiguration of data placement in a storage area network ⋮ The class constrained bin packing problem with applications to video-on-demand ⋮ A one-dimensional bin packing problem with shelf divisions ⋮ Class constrained bin covering ⋮ Algorithms for storage allocation based on client preferences ⋮ Class constrained bin packing revisited ⋮ Lower bounds for several online variants of bin packing ⋮ The multiple multidimensional knapsack with family-split penalties ⋮ A note on dual approximation algorithms for class constrained bin packing problems ⋮ Bin packing with directed stackability conflicts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Design and implementation of scalable continuous media servers
• Bin packing can be solved within 1+epsilon in linear time
• Approximate algorithms for some generalized knapsack problems
• An approximation algorithm for the generalized assignment problem
• Approximation algorithms for knapsack problems with cardinality constraints
• Multiresource malleable task scheduling to minimize response time
• Cardinality constrained bin-packing problems
• A heuristic routine for solving large loading problems
• An Algorithm for the Solution of 0-1 Loading Problems
• Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• `` Strong NP-Completeness Results
• Solving Multiple Knapsack Problems by Cutting Planes
• On two class-constrained versions of the multiple knapsack problem

This page was built for publication: Polynomial time approximation schemes for class-constrained packing problems