Improved Approximation Algorithm for Two-Dimensional Bin Packing

No abstract is available for this paper.

• Publication year

  2014

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2014-01-05

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/1.9781611973402.2
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Approximating Bin Packing within O(log OPT * Log Log OPT) Bins

  2013cited by this paper
• Approximation Algorithms for Geometric Packing Problems

  2013cited by this paper
• TwoForOneRevised Two for One : Tight approximation of 2

  2013cited by this paper
• New Approximability Results for Two-Dimensional Bin Packing

  2013cited by this paper
• Two for One: Tight Approximation of 2D Bin Packing

  2009cited by this paper
• A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing

  2009cited by this paper
• A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability

  2009cited by this paper
• Rectangle packing with one-dimensional resource augmentation

  2009cited by this paper
• Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems

  2007cited by this paper
• Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations

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

  2006cited by this paper
• Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing

  2005cited by this paper
• A tale of two dimensional bin packing

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

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

  2000cited by this paper
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem

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

  1991cited by this paper
• Geometric Algorithms and Combinatorial Optimization

  1988cited by this paper
• Minkowski's Convex Body Theorem and Integer Programming

  1987cited by this paper
• A simple on-line bin-packing algorithm

  1985cited by this paper
• On Packing Two-Dimensional Bins

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

  1982cited by this paper
• The NP-Completeness Column: An Ongoing Guide

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

  1981cited by this paper
• Analysis and design of algorithms in combinatorial optimization

  1981cited by this paper
• Approximation Algorithms for Bin Packing Problems: A Survey

  1981cited 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
• Algorithm for solution of a problem of maximal flow in a network with power estimation

  1970cited by this paper

• On the 2D Demand Bin Packing Problem: Hardness and Approximation Algorithms

  2025cites this paper
• Tight Approximation Algorithms for 2D Guillotine Strip Packing

  2025influential citation
• Improved Approximation Algorithms for Three-Dimensional Bin Packing

  2025influential citation
• Improved Approximation Guarantees for Advertisement Placement

  2025cites this paper
• Random-Order Online Independent Set of Intervals and Hyperrectangles

  2024cites this paper
• A Framework for Efficient Approximation Schemes on Geometric Packing Problems of $d$-dimensional Fat Objects

  2024cites this paper
• Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects

  2024cites this paper
• On Approximation Schemes for Stabbing Rectilinear Polygons

  2024cites this paper
• A Tight $$(3/2+\varepsilon )$$ ( 3 / 2 + ε )

  2023cites this paper
• An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding

  2023cites this paper
• Improved Approximations for Translational Packing of Convex Polygons

  2023cites this paper
• Tight Bounds for Budgeted Maximum Weight Independent Set in Bipartite and Perfect Graphs

  2023cites this paper
• Improved Hardness of Approximation for Geometric Bin Packing

  2023influential citation
• A 3-Approximation Algorithm for Maximum Independent Set of Rectangles

  2022cites this paper
• Approximation Algorithms for ROUND-UFP and ROUND-SAP

  2022influential citation
• (Re)packing Equal Disks into Rectangle

  2022influential citation
• A Time-Efficient and Exploratory Algorithm for the Rectangle Packing Problem

  2022cites this paper
• On-line three-dimensional packing problems: A review of off-line and on-line solution approaches

  2022cites this paper
• A PTAS for Packing Hypercubes into a Knapsack

  2022cites this paper
• Tight Approximation Algorithms for Two Dimensional Guillotine Strip Packing

  2022influential citation
• A Model Simplification Algorithm for 3D Reconstruction

  2022cites this paper
• On Guillotine Separable Packings for the Two-dimensional Geometric Knapsack Problem

  2021cites this paper
• Approximation Algorithms for Generalized Multidimensional Knapsack

  2021cites this paper
• Almost Optimal Inapproximability of Multidimensional Packing Problems

  2021cites this paper
• A better lower bound for Lower-Left Anchored Rectangle Packing

  2021cites this paper
• A PTAS for the horizontal rectangle stabbing problem

  2021cites this paper
• A (2+\epsilon)-Approximation Algorithm for Maximum Independent Set of Rectangles

  2021cites this paper
• LraSched: Admitting More Long-Running Applications via Auto-Estimating Container Size and Affinity

  2021cites this paper
• Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing

  2021influential citation
• Peak Demand Minimization via Sliced Strip Packing

  2021cites this paper
• Tight Approximation Algorithms for Geometric Bin Packing with Skewed Items

  2021influential citation
• Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More

  2021cites this paper
• Harmonic algorithms for packing d-dimensional cuboids into bins

  2020cites this paper
• Framework for ∃ ℝ-Completeness of Two-Dimensional Packing Problems

  2020cites this paper
• Framework for ER-Completeness of Two-Dimensional Packing Problems

  2020cites this paper
• On Guillotine Separability of Squares and Rectangles

  2020cites this paper
• An Approximation Algorithm for Covering Linear Programs and its Application to Bin-Packing

  2020cites this paper
• Improved Approximation Algorithms for Weighted Edge Coloring of Graphs

  2020cites this paper
• Robust Online Algorithms for Dynamic Problems

  2019influential citation
• A Variable Neighborhood Search Algorithm for Two-Dimensional Bin Packing Problem with Compatible Categories

  2019cites this paper
• A Hybrid PSO-LS approach for solving the Two-Dimensional Bin Packing Problem with weight capacities constraint: A case study

  2019cites this paper
• Robust Online Algorithms for Certain Dynamic Packing Problems

  2019cites this paper
• On the Complexity of Anchored Rectangle Packing

  2019cites this paper
• Improved Pseudo-Polynomial-Time Approximation for Strip Packing

  2018cites this paper
• A two-dimensional bin packing-based split-and-pack approach for decomposing large three-dimensional structures into convex items

  2018cites this paper
• Algorithms for load balancing in electricity markets and data centers

  2018influential citation
• Colocation, Colocation, Colocation: Optimizing Placement in the Hybrid Cloud

  2018cites this paper
• A Tale of Two Packing Problems: Improved Algorithms and Tighter Bounds for Online Bin Packing and the Geometric Knapsack Problem

  2018influential citation
• Elasecutor: Elastic Executor Scheduling in Data Analytics Systems

  2018cites this paper
• Online Circle and Sphere Packing

  2017influential citation
• The Inverse Bin-Packing Problem Subject to Qualitative Criteria

  2017cites this paper
• Faster Approximation Schemes for the Two-Dimensional Knapsack Problem

  2017cites this paper
• Approximation and online algorithms for multidimensional bin packing: A survey

  2017cites this paper
• Closing the gap for pseudo-polynomial strip packing

  2017cites this paper
• Approximating Geometric Knapsack via L-Packings

  2017cites this paper
• Approximating Smallest Containers for Packing Three-Dimensional Convex Objects

  2016cites this paper
• Improved Approximation for Vector Bin Packing

  2016influential citation
• Anchored rectangle and square packings

  2016cites this paper
• A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem

  2015cites this paper
• On the number of anchored rectangle packings for a planar point set

  2015cites this paper
• Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2D bin packing problems

  2015cites this paper
• Polynomial-Time Approximation Schemes for Circle Packing Problems

  2014cites this paper
• Almost Online Square Packing

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

  2014cites this paper
• Alternative Approaches for Analysis of Bin Packing and List Update Problems

  2014cites this paper
• Polynomial-Time Approximation Schemes for Circle and Other Packing Problems

  2014influential citation
• New Approximability Results for Two-Dimensional Bin Packing

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

  2013influential citation
• Research on Bin Packing Problem Based on Supply Chain Economic Efficiency

  year unknowninfluential citation
• This paper is included in the Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI ’16).

  year unknowncites this paper