A constant factor approximation algorithm for the storage allocation problem
From MaRDI portal
Publication:524369
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
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items
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