Copertina

Hardness and Tight Approximations of Demand Strip Packing

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Jansen, Klaus, Rau, Malin, Tutas, Malte
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

A Tight ($3/2 + \varepsilon$)-Approximation Algorithm for Demand Strip Packing
di: Eberle, Franziska, et al.
Pubblicazione: (2024)

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

New Algorithm for Combinatorial $n$-folds and Applications
di: Jansen, Klaus, et al.
Pubblicazione: (2024)

FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares
di: Jansen, Klaus, et al.
Pubblicazione: (2024)

Improved Approximation Algorithms for Three-Dimensional Knapsack
di: Jansen, Klaus, et al.
Pubblicazione: (2025)

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

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

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

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

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

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

A Practical 73/50 Approximation for Contiguous Monotone Moldable Job Scheduling
di: Jansen, Klaus, et al.
Pubblicazione: (2026)

Equivalent Instances for Scheduling and Packing Problems
di: Jansen, Klaus, et al.
Pubblicazione: (2025)

Hitting Meets Packing: How Hard Can it Be?
di: Focke, Jacob, et al.
Pubblicazione: (2024)

Improved Hardness of Approximation for Geometric Bin Packing
di: Ray, Arka, et al.
Pubblicazione: (2023)

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

Robust Scheduling on Uniform Machines -- New Results Using a Relaxed Approximation Guarantee
di: Brinkop, Hauke, et al.
Pubblicazione: (2025)

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

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

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

Hardness and Approximation for Coloring Digraphs
di: Chalermsook, Parinya, et al.
Pubblicazione: (2026)

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

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

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

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

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

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

Hardness and Approximation Algorithms for Balanced Districting Problems
di: Dharangutte, Prathamesh, et al.
Pubblicazione: (2025)

Hardness of Approximation for Shortest Path with Vector Costs
di: Carlson, Charlie, et al.
Pubblicazione: (2025)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2023)

Approximating Energy-Constrained Drone Delivery Packing Problem for Last-Mile Logistics
di: Jana, Saswata, et al.
Pubblicazione: (2026)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
di: Jiang, Yonggang, et al.
Pubblicazione: (2025)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
di: Mömke, Tobias, et al.
Pubblicazione: (2024)

Automating the Search for Small Hard Examples to Approximation Algorithms
di: Sharma, Eklavya
Pubblicazione: (2025)

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

Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings
di: Kyng, Rasmus, et al.
Pubblicazione: (2025)

Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities
di: Lokshtanov, Daniel, et al.
Pubblicazione: (2024)

Sorting by Strip Swaps is NP-Hard
di: Roy, Swapnoneel, et al.
Pubblicazione: (2025)

Improved Approximation Algorithms and Hardness Results for Shortest Common Superstring with Reverse Complements
di: Yamano, Ryosuke, et al.
Pubblicazione: (2026)

Convolution and Knapsack in Higher Dimensions
di: Grage, Kilian, et al.
Pubblicazione: (2024)