Cover Image

A Tight ($3/2 + \varepsilon$)-Approximation Algorithm for Demand Strip Packing

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Eberle, Franziska, Hommelsheim, Felix, Rau, Malin, Walzer, Stefan
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Hardness and Tight Approximations of Demand Strip Packing
by: Jansen, Klaus, et al.
Published: (2024)

Improved Approximation Algorithms for Three-Dimensional Bin Packing
by: Kar, Debajyoti, et al.
Published: (2025)

A Better-Than-$5/4$-Approximation for Two-Edge Connectivity
by: Hommelsheim, Felix, et al.
Published: (2025)

Accelerating Matroid Optimization through Fast Imprecise Oracles
by: Eberle, Franziska, et al.
Published: (2024)

On the 2D Demand Bin Packing Problem: Hardness and Approximation Algorithms
by: Albers, Susanne, et al.
Published: (2025)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Two-Edge Connectivity via Pac-Man Gluing
by: Garg, Mohit, et al.
Published: (2024)

The Probability to Hit Every Bin with a Linear Number of Balls
by: Walzer, Stefan
Published: (2024)

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
by: Zhao, Jingyang, et al.
Published: (2025)

An Improved Approximation Algorithm for Metric Triangle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

Improved Approximation Algorithms for the Expanding Search Problem
by: Griesbach, Svenja M., et al.
Published: (2023)

An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange
by: Jansen, Bart M. P., et al.
Published: (2025)

Approximation Algorithms for Packing Cycles and Paths in Complete Graphs
by: Zhao, Jingyang, et al.
Published: (2023)

A $(4/3+\varepsilon)$-Approximation for Preemptive Scheduling with Batch Setup Times
by: Deppert, Max A., et al.
Published: (2025)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
by: Bringmann, Karl, et al.
Published: (2026)

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
by: Das, Rathish, et al.
Published: (2025)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
by: Chen, Lin, et al.
Published: (2026)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
by: Dai, Han, et al.
Published: (2025)

Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond
by: Fischer, Manuela, et al.
Published: (2021)

Better space-time-robustness trade-offs for set reconciliation
by: Belazzougui, Djamal, et al.
Published: (2024)

Testing Depth First Search Numbering
by: Czumaj, Artur, et al.
Published: (2025)

Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
by: Ahmadi, Ali, et al.
Published: (2025)

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
by: An, Shinwoo, et al.
Published: (2024)

Deterministic $(2/3-\varepsilon)$-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries
by: Terao, Tatsuya
Published: (2024)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
by: Jansen, Klaus, et al.
Published: (2025)

ShockHash: Near Optimal-Space Minimal Perfect Hashing Beyond Brute-Force
by: Lehmann, Hans-Peter, et al.
Published: (2023)

A $(3+\varepsilon)$-Approximate Correlation Clustering Algorithm in Dynamic Streams
by: Cambus, Mélanie, et al.
Published: (2022)

Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands
by: Zhao, Jingyang, et al.
Published: (2025)

Tight Sampling Bounds for Eigenvalue Approximation
by: Swartworth, William, et al.
Published: (2024)

Approximations and Hardness of Packing Partially Ordered Items
by: Doron-Arad, Ilan, et al.
Published: (2024)

Combined Search and Encoding for Seeds, with an Application to Minimal Perfect Hashing
by: Lehmann, Hans-Peter, et al.
Published: (2025)

Scalable Algorithms for 2-Packing Sets on Arbitrary Graphs
by: Borowitz, Jannick, et al.
Published: (2023)

Engineering Minimal k-Perfect Hash Functions
by: Hermann, Stefan, et al.
Published: (2025)

Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
by: Hommelsheim, Felix
Published: (2025)

PHOBIC: Perfect Hashing with Optimized Bucket Sizes and Interleaved Coding
by: Hermann, Stefan, et al.
Published: (2024)

Scheduling on a Stochastic Number of Machines
by: Buchem, Moritz, et al.
Published: (2024)

Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures
by: Hommelsheim, Felix, et al.
Published: (2025)

The Support of Bin Packing is Exponential
by: Jansen, Klaus, et al.
Published: (2025)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time
by: Armbruster, Alexander, et al.
Published: (2025)