On Multidimensional Packing Problems

DOI10.1137/S0097539799356265zbMath1101.68606OpenAlexW2042276676MaRDI QIDQ4651495

Sanjeev Khanna, Chandra Chekuri

Publication date: 21 February 2005

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

Full work available at URL: https://doi.org/10.1137/s0097539799356265

zbMATH Keywords

combinatorial optimizationmultiprocessor schedulingapproximation algorithmsknapsackbin packinghardness of approximationpacking integer programsvector bin packingvector schedulingmultidimensional packing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (32)

Vector scheduling with rejection on two machines ⋮ Shrinking maxima, decreasing costs: new online packing and covering problems ⋮ Selfish Vector Packing ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ Greedy algorithms for the profit-aware social team formation problem ⋮ Scheduling selfish jobs on multidimensional parallel machines ⋮ A Service System with Packing Constraints: Greedy Randomized Algorithm Achieving Sublinear in Scale Optimality Gap ⋮ There is no APTAS for 2-dimensional vector bin packing: revisited ⋮ A state-of-the-art survey on multi-scenario scheduling ⋮ Approximation schemes for generalized two-dimensional vector packing with application to data placement ⋮ Vector bin packing with multiple-choice ⋮ Online two-dimensional vector packing with advice ⋮ Minimizing worst-case and average-case makespan over scenarios ⋮ Online vector scheduling and generalized load balancing ⋮ Tight Bounds for Online Vector Scheduling ⋮ Scheduling split intervals with non-uniform demands ⋮ Distributed approximation of \(k\)-service assignment ⋮ Resource allocation algorithms for virtualized service hosting platforms ⋮ Selfish vector packing ⋮ Vector scheduling with rejection on a single machine ⋮ Integer programming models for mid-term production planning for high-tech low-volume supply chains ⋮ Resource augmentation for uniprocessor and multiprocessor partitioned scheduling of sporadic real-time tasks ⋮ Mixed-criticality scheduling on multiprocessors ⋮ Unnamed Item ⋮ Approximating vector scheduling: almost matching upper and lower bounds ⋮ Approximation Schemes for Robust Makespan Scheduling Problems ⋮ \(\ell_1\)-sparsity approximation bounds for packing integer programs ⋮ Streaming algorithms for bin packing and vector scheduling ⋮ An EPTAS for scheduling on unrelated machines of few different types ⋮ Running Errands in Time: Approximation Algorithms for Stochastic Orienteering ⋮ Truthful mechanism design for bin packing with applications on cloud computing ⋮ On capacitated covering with unit balls

This page was built for publication: On Multidimensional Packing Problems