A constant factor approximation algorithm for the storage allocation problem

DOI10.1007/S00453-016-0137-8zbMath1364.68365OpenAlexW2290717180MaRDI QIDQ524369

Michael Beder, Dror Rawitz, Reuven Bar Yehuda

Publication date: 2 May 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-016-0137-8

zbMATH Keywords

approximation algorithmsbandwidth allocationrectangle packingunsplittable flowstorage allocation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (3)

A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem ⋮ A constant factor approximation algorithm for the storage allocation problem ⋮ Flexible resource allocation to interval jobs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A constant factor approximation algorithm for the storage allocation problem
• Caching is hard -- even in the fault model
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Approximation algorithms for the unsplittable flow problem
• Resource allocation in bounded degree trees
• A quasi-PTAS for unsplittable flow on line graphs
• A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem
• Multicommodity demand flow in a tree and packing integer programs
• Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
• Smallest-last ordering and clustering and graph coloring algorithms
• OPTVersusLOADin Dynamic Storage Allocation
• Constant Integrality Gap LP Formulations of Unsplittable Flow on a Path
• On Linear Programming Relaxations for Unsplittable Flow in Trees
• New Approximation Schemes for Unsplittable Flow on a Path
• A Mazing 2+∊ Approximation for Unsplittable Flow on a Path
• A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths
• A logarithmic approximation for unsplittable flow on line graphs
• A unified approach to approximating resource allocation and scheduling
• The complexity of path coloring and call scheduling

This page was built for publication: A constant factor approximation algorithm for the storage allocation problem