OPTVersusLOADin Dynamic Storage Allocation

DOI10.1137/S0097539703423941zbMath1101.68599MaRDI QIDQ4651485

Mikkel Thorup, Nick Reingold, Howard J. Karloff, Claire M. Kenyon, Adam L. Buchsbaum

Publication date: 21 February 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

approximation algorithms; polynomial-time approximation schemes; dynamic storage allocation

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

Related Items

An Improved Upper Bound for the Ring Loading Problem, Optimizing active ranges for consistent dynamic map labeling, A constant factor approximation algorithm for the storage allocation problem, First-fit coloring of bounded tolerance graphs, Clique clustering yields a PTAS for max-coloring interval graphs, Strip packing with precedence constraints and strip packing with release times, Scheduling with conflicts: Online and offline algorithms, About equivalent interval colorings of weighted graphs, Resource allocation in bounded degree trees, On spectrum assignment in elastic optical tree-networks, Flexible resource allocation to interval jobs, Profit maximization in flex-grid all-optical networks, On the interval chromatic number of proper interval graphs, Optimizing bandwidth allocation in elastic optical networks with application to scheduling, Profit Maximization in Flex-Grid All-Optical Networks, On minimizing dataset transfer time in an acyclic network with four servers, A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem