A unified approach to approximating resource allocation and scheduling

DOI10.1145/502102.502107zbMath1323.68564WikidataQ56267426 ScholiaQ56267426MaRDI QIDQ5895231

Baruch Schieber, Ari Freund, Joseph (Seffi) Naor, Amotz Bar-Noy, 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

90B35: Deterministic scheduling theory in operations research

68W25: Approximation algorithms

91B32: Resource and cost allocation (including fair division, apportionment, etc.)

Related Items

A Novel Approximate Algorithm for Admission Control, Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems, Online scheduling with interval conflicts, Distributed approximation of cellular coverage, Improving LTL truck load utilization on line, Resource allocation with time intervals, Combination of parallel machine scheduling and vertex cover, Real time scheduling with a budget: parametric-search is better than binary search, An efficient approximation for the generalized assignment problem, Fixed interval scheduling: models, applications, computational complexity and algorithms, Using fractional primal-dual to schedule split intervals with demands, The tool switching problem revisited, Exploiting locality: Approximating sorting buffers, Approximating the 2-interval pattern problem, Elementary approximation algorithms for prize collecting Steiner tree problems, Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs, Resource allocation in bounded degree trees, Conversion of coloring algorithms into maximum weight independent set algorithms, Fast primal-dual distributed algorithms for scheduling and matching problems, Admission control with advance reservations in simple networks, On Tree-Constrained Matchings and Generalizations, On Variants of File Caching, 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