A unified approach to approximating resource allocation and scheduling
From MaRDI portal
Publication:5895231
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
scheduling; resource allocation; approximation algorithms; NP-hard problems; dynamic storage allocation; general caching
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, Improving LTL truck load utilization on line, Resource allocation with time intervals, 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, 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