Improved approximation algorithms for multidimensional bin packing problems

No abstract is available for this paper.

• Publication year

  2006

• Venue

  IEEE Annual Symposium on Foundations of Computer Science

• Publication date

  2006-10-21

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/FOCS.2006.38
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Multidimensional Packing Problems

  2018influential reference
• Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem

  2007cited by this paper
• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes

  2006influential reference
• Bidimensional packing by bilinear programming

  2005cited by this paper
• On strip packing With rotations

  2005influential reference
• On rectangle packing: maximizing benefits

  2004influential reference
• An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing

  2003cited by this paper
• Packing 2-dimensional bins in harmony

  2002cited by this paper
• Lower bounds and algorithms for the 2-dimensional vector packing problem

  2001cited by this paper
• Approximate Max-Min Resource Sharing for Structured Concave Optimization

  2000influential reference
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem

  2000cited by this paper
• Probabilistic methods for algorithmic discrete mathematics

  1998cited by this paper
• There is no Asymptotic PTAS for Two-Dimensional Vector Packing

  1997cited by this paper
• Fast approximation algorithms for fractional packing and covering problems

  1991influential reference
• GEOMETRIC ALGORITHMS AND COMBINATORIAL OPTIMIZATION: (Algorithms and Combinatorics 2)

  1990influential reference
• Surveys in Combinatorics, 1989: On the method of bounded differences

  1989cited by this paper
• Geometric Algorithms and Combinatorial Optimization

  1988influential reference
• A simple on-line bin-packing algorithm

  1985cited by this paper
• Approximation algorithms for the m-dimensional 0–1 knapsack problem: Worst-case and probabilistic analyses

  1984cited by this paper
• An efficient approximation scheme for the one-dimensional bin-packing problem

  1982cited by this paper
• Bin packing can be solved within 1 + ε in linear time

  1981cited by this paper
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms

  1980cited by this paper

• Approximation Algorithms for Fair Repetitive Scheduling

  2025cites this paper
• Online Job Assignment

  2024cites this paper
• Summary : A natural generalization of the classical online bin packing problem is the dynamic bin packing problem introduced

  2022cites this paper
• A multidimensional colored packing approach for network slicing with dedicated protection

  2021cites this paper
• A Resource-aware Container Management Scheme in a Heterogeneous Cluster

  2021cites this paper
• Building Scalable and Flexible Cluster Managers Using Declarative Programming

  2020cites this paper
• Automating Cluster Management with Weave

  2019cites this paper
• RPBG: Intelligent Orchestration Strategy of Heterogeneous Docker Cluster Based on Graph Theory

  2019cites this paper
• Online packing of arbitrary sized items into designated and multipurpose bins

  2019cites this paper
• Leveraging content similarity among VMI files to allocate virtual machines in cloud

  2018cites this paper
• A Provident Resource Defragmentation Framework for Mobile Cloud Computing

  2018cites this paper
• Virtual machine placement with (m, n)-fault tolerance in cloud data center

  2017influential citation
• DRAPS: Dynamic and resource-aware placement scheme for docker containers in a heterogeneous cluster

  2017influential citation
• Network failure–aware redundant virtual machine placement in a cloud data center

  2017cites this paper
• Packing into designated and multipurpose bins: A theoretical study and application to the cold chain☆

  2017cites this paper
• Minimum-latency communication in wireless mesh networks under noisy physical interference model

  2017influential citation
• Online Lower Bounds via Duality

  2016cites this paper
• An energy-optimization-based method of task scheduling for a cloud video surveillance center

  2016cites this paper
• Migrations en temps réel des machines virtuelles interdépendantes

  2016influential citation
• Improved Approximation for Vector Bin Packing

  2016cites this paper
• Vector bin packing with heterogeneous bins: application to the machine reassignment problem

  2015cites this paper
• Heuristics for Multidimensional Packing Problems

  2015cites this paper
• Minimizing takeoff and landing risk in helicopter pickup and delivery operations

  2015cites this paper
• Real-Time Task Scheduling on Island-Based Multi-Core Platforms

  2015cites this paper
• Multi-resource energy-efficient routing in cloud data centers with network-as-a-service

  2015cites this paper
• Decision Diagrams for Combinatorial Optimization and Satisfaction

  2015cites this paper
• Two-Dimensional Bin Packing Problem with Guillotine Restrictions

  2015cites this paper
• Online Square-into-Square Packing

  2014cites this paper
• GeNePi: A Multi-Objective Machine Reassignment Algorithm for Data Centres

  2014cites this paper
• Two‐Dimensional Bin Packing Problems

  2014cites this paper
• Online dynamic bin packing

  2014cites this paper
• High-Multiplicity Scheduling and Packing Problems

  2014influential citation
• MÔ HÌNH NỀN TẢNG MÁY CHỦ CHIA SẺ VÀ BÀI TOÁN VECTOR PACKING TRONG CUNG CẤP TÀI NGUYÊN CHO DỊCH VỤ ẢO HÓA

  2014influential citation
• Making Decisions Under Uncertainty for Large Data Domains

  2014cites this paper
• High-multiplicity Scheduling and Packing Problems : Theory and Applications

  2014influential citation
• 5. Two-Dimensional Bin Packing Problems

  2013cites this paper
• Online Multidimensional Load Balancing

  2013cites this paper
• Vector repacking algorithms for power-aware computing

  2013cites this paper
• A Harmonic Algorithm for the 3D Strip Packing Problem

  2013cites this paper
• Non-cooperative games on multidimensional resource allocation

  2013cites this paper
• Online algorithms for 1-space bounded multi dimensional bin packing and hypercube packing

  2013cites this paper
• Dynamic optimization of virtual machine placement by resource usage prediction

  2013cites this paper
• Using matrix approximation for high-dimensional discrete optimization problems: Server consolidation based on cyclic time-series data

  2013cites this paper
• Optimizing Resource allocation while handling SLA violations in Cloud Computing platforms

  2013cites this paper
• On Packing Almost Half of a Square with Anchored Rectangles: A Constructive Approach

  2013cites this paper
• Multidimensional Bin Packing Revisited

  2013cites this paper
• Variable size vector bin packing heuristics - Application to the machine reassignment problem

  2013cites this paper
• On the weak computability of a four dimensional orthogonal packing and time scheduling problem

  2013cites this paper
• Title Online algorithms for 1-space bounded multi dimensional binpacking and hypercube packing

  2013influential citation
• Heuristic algorithms for wireless mesh network planning

  2012cites this paper
• Offline algorithms and difficulties

  2012cites this paper
• Using hidden space in optimization of space utilization

  2012cites this paper
• Absolute approximation ratios for packing rectangles into bins

  2012influential citation
• A multi-objective scheduling strategy based on MOGA in cloud computing environment

  2012cites this paper
• CSIS 801 Final Year Project Report

  2012cites this paper
• Optimal Vector Packing in Multiple Dimensions with Heuristic Search

  2012cites this paper
• Joint Admission Control, Channel Assignment and QoS Routing for Coverage Optimization in Multi-Hop Cognitive Radio Cellular Networks

  2011influential citation
• Self-organizing sensing infrastructure for autonomic management of green datacenters

  2011cites this paper
• Online Algorithm for 1-Space Bounded Multi-dimensional Bin Packing

  2011cites this paper
• Service deactivation aware placement and defragmentation in enterprise clouds

  2011cites this paper
• Heuristics for Vector Bin Packing

  2011cites this paper
• Approximation algorithms for scheduling and two-dimensional packing problems

  2010cites this paper
• Latency-Efficient Distributed M2M Multicasting in Wireless Mesh Networks under Physical Interference Model

  2010influential citation
• Study on improved ant colony optimization for bin-packing problem

  2010cites this paper
• Minimum-Latency Communication in Wireless Mesh Networks under Physical Interference Model

  2010influential citation
• Vector Bin Packing with Multiple-Choice (Extended Abstract)

  2010influential citation
• Dynamic Fractional Resource Scheduling for cluster platforms

  2010cites this paper
• One-Space Bounded Algorithms for Two-Dimensional Bin Packing

  2010cites this paper
• Improved Online Algorithms for 1-Space Bounded 2-Dimensional Bin Packing

  2010cites this paper
• Gateway selection scheme for throughput optimization in multi-radio multi-channel wireless mesh networks under physical interference model

  2010influential citation
• A Mathematical Programming Approach for Server Consolidation Problems in Virtualized Data Centers

  2010cites this paper
• Improved approximation bounds for Vector Bin Packing

  2010cites this paper
• Resource allocation algorithms for virtualized service hosting platforms

  2010influential citation
• Dynamic fractional resource scheduling for HPC workloads

  2010cites this paper
• Optimal Placement Algorithms for Virtual Machines

  2010cites this paper
• Dynamic multi-dimensional bin packing

  2010influential citation
• Rectangle packing with one-dimensional resource augmentation

  2009cites this paper
• Approximation algorithms for orthogonal packing problems for hypercubes

  2009cites this paper
• An Absolute 2-Approximation Algorithm for Two-Dimensional Bin Packing

  2009influential citation
• Two for One: Tight Approximation of 2D Bin Packing

  2009influential citation
• A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability

  2009influential citation
• Competitive Multi-dimensional Dynamic Bin Packing via L-Shape Bin Packing

  2009cites this paper
• Vector bin packing with multiple-choice

  2009influential citation
• A New Upper Bound on 2D Online Bin Packing

  2009cites this paper
• 1-Bounded Space Algorithms for 2-Dimensional Bin Packing

  2009cites this paper
• Bin-packing multi-depots vehicle scheduling problem and its ant colony optimization

  2009cites this paper
• Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems

  2009influential citation
• Absolute approximation ratios for packing rectangles into bins

  2009influential citation
• Joint QoS-aware admission control, channel assignment, and power allocation for cognitive radio cellular networks

  2009influential citation
• Packing Rectangles into 2OPT Bins Using Rotations

  2008influential citation
• Packing d-Dimensional Bins in d Stages

  2008cites this paper
• Algorithm Theory - SWAT 2008, 11th Scandinavian Workshop on Algorithm Theory, Gothenburg, Sweden, July 2-4, 2008, Proceedings

  2008cites this paper
• Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems

  2007cites this paper
• Harmonic algorithm for 3-dimensional strip packing problem

  2007cites this paper
• Approximation Algorithms for 3D Orthogonal Knapsack

  2007cites this paper
• Bidimensional packing by bilinear programming

  2005cites this paper
• VMware distributed resource Management : design , Implementation , and lessons learned

  year unknowncites this paper