A unified approach to approximating resource allocation and scheduling

DOI10.1145/502102.502107zbMath1323.68564OpenAlexW2003902046WikidataQ56267426 ScholiaQ56267426MaRDI QIDQ5895231

Ari Freund, Joseph (Seffi) Naor, Amotz Bar-Noy, Baruch Schieber, Reuven Bar Yehuda

Publication date: 30 October 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/502102.502107

zbMATH Keywords

scheduling resource allocation approximation algorithms NP-hard problems dynamic storage allocation general caching

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items (73)

Improved algorithms for resource allocation under varying capacity ⋮ Flexible bandwidth assignment with application to optical networks ⋮ A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem ⋮ Dynamic resource allocation: a flexible and tractable modeling framework ⋮ Fast primal-dual distributed algorithms for scheduling and matching problems ⋮ Real time scheduling with a budget: parametric-search is better than binary search ⋮ An efficient approximation for the generalized assignment problem ⋮ A Water-Filling Primal-Dual Algorithm for Approximating NonLinear Covering Problems ⋮ Increasing the revenue of self-storage warehouses by optimizing order scheduling ⋮ Resource allocation problem under single resource assignment ⋮ Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ Inverse interval scheduling via reduction on a single machine ⋮ Using fractional primal-dual to schedule split intervals with demands ⋮ A Novel Approximate Algorithm for Admission Control ⋮ Succinct encodings for families of interval graphs ⋮ Online scheduling with interval conflicts ⋮ Optimizing bandwidth allocation in elastic optical networks with application to scheduling ⋮ General caching is hard: even with small pages ⋮ Resource allocation with time intervals ⋮ The tool switching problem revisited ⋮ Caching with Time Windows and Delays ⋮ A truthful mechanism for value-based scheduling in cloud computing ⋮ Chronological rectangle digraphs which are two-terminal series-parallel ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ Approximations for generalized unsplittable flow on paths with application to power systems optimization ⋮ Polynomial Kernel for Interval Vertex Deletion ⋮ A combinatorial flow-based formulation for temporal bin packing problems ⋮ Mobility offer allocations in corporate settings ⋮ Improved algorithms for scheduling unsplittable flows on paths ⋮ On improved interval cover mechanisms for crowdsourcing markets ⋮ On streaming algorithms for geometric independent set and clique ⋮ Distributed approximation of cellular coverage ⋮ Fixed-parameter algorithms for unsplittable flow cover ⋮ Unnamed Item ⋮ Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time ⋮ Scheduling split intervals with non-uniform demands ⋮ Approximation algorithm for the minimum weight connected $k$-subgraph cover problem ⋮ Exploiting locality: Approximating sorting buffers ⋮ Complex-demand scheduling problem with application in smart grid ⋮ Optimizing busy time on parallel machines ⋮ Approximating the 2-interval pattern problem ⋮ Distributed approximation of $k$-service assignment ⋮ Bandwidth allocation in cellular networks with multiple interferences ⋮ Admission control with advance reservations in simple networks ⋮ On Tree-Constrained Matchings and Generalizations ⋮ On Variants of File Caching ⋮ How unsplittable-flow-covering helps scheduling with job-dependent cost functions ⋮ Maximizing Throughput in Flow Shop Real-Time Scheduling ⋮ A constant factor approximation algorithm for the storage allocation problem ⋮ Combination of parallel machine scheduling and vertex cover ⋮ Improving LTL truck load utilization on line ⋮ Elementary approximation algorithms for prize collecting Steiner tree problems ⋮ Unnamed Item ⋮ Approximating maximum weight $K$-colorable subgraphs in chordal graphs ⋮ Conversion of coloring algorithms into maximum weight independent set algorithms ⋮ Pricing on Paths: A PTAS for the Highway Problem ⋮ The Prize-collecting Call Control Problem on Weighted Lines and Rings ⋮ Computing a maximum clique in geometric superclasses of disk graphs ⋮ Flexible allocation on related machines with assignment restrictions ⋮ Primal-dual schema for capacitated covering problems ⋮ On Capacitated Set Cover Problems ⋮ Scheduling Resources for Throughput Maximization ⋮ A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems ⋮ Resource Management in Large Networks ⋮ Resource allocation in bounded degree trees ⋮ Unnamed Item ⋮ Set cover problems with small neighborhood covers ⋮ A logarithmic approximation for unsplittable flow on line graphs ⋮ Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems ⋮ Unnamed Item ⋮ Online file caching with rejection penalties ⋮ Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time ⋮ A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems

This page was built for publication: A unified approach to approximating resource allocation and scheduling