Breaking the barrier of 2 for the storage allocation problem

DOI10.4230/LIPICS.ICALP.2020.86MaRDI QIDQ6842485zbMATH OpenFDO

Authors Tobias Mömke, Andreas Wiese

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.86

zbMATH Keywords

approximation algorithmsdynamic programmingresource allocation

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• OPTVersusLOADin Dynamic Storage Allocation
• A (2+)-approximation algorithm for the storage allocation problem
• A (5/3+)-approximation for unsplittable flow on a path: placing small tasks into boxes
• A constant factor approximation algorithm for the storage allocation problem
• A constant-factor approximation algorithm for unsplittable flow on paths
• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
• A polynomial time approximation algorithm for dynamic storage allocation
• A Polynomial Time Approximation Scheme for the Square Packing Problem
• A quasi-PTAS for the two-dimensional geometric knapsack problem
• A quasi-PTAS for unsplittable flow on line graphs
• A structural lemma in 2-dimensional packing, and its implications on approximability
• A unified approach to approximating resource allocation and scheduling
• Algorithm Theory - SWAT 2004
• An improved approximation algorithm for \textsc{Resource Allocation}
• Approximating geometric knapsack via L-packings
• Approximation algorithms for dynamic storage allocation
• Approximation algorithms for the unsplittable flow problem
• Faster approximation schemes for the two-dimensional knapsack problem
• scientific article; zbMATH DE number 1305512 (Why is no real title available?)
• scientific article; zbMATH DE number 7051239 (Why is no real title available?)
• scientific article; zbMATH DE number 1445390 (Why is no real title available?)
• Maximizing the total profit of rectangles packed into a rectangle
• Multicommodity demand flow in a tree and packing integer programs
• New approximation schemes for unsplittable flow on a path
• Resource allocation in bounded degree trees
• The Linearity of First-Fit Coloring of Interval Graphs
• To augment or not to augment: solving unsplittable flow on a path by creating slack
• Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs

Cited in

(3)

• Approximation algorithms for round-UFP and round-SAP
• On guillotine separable packings for the two-dimensional geometric knapsack problem
• Random-order online independent set of intervals and hyperrectangles

This page was built for publication: Breaking the barrier of 2 for the storage allocation problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6842485)