A unified approach to approximating resource allocation and scheduling

DOI10.1145/335305.335410MaRDI QIDQ5895207zbMATH OpenOpenAlexFDO

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

Publication date 26 September 2014

Published in Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

bandwidth allocationinterval graphsinterval schedulingresource allocationscheduling with release times and deadlines

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Recommendations

• A unified approach to approximating resource allocation and scheduling
• scientific article; zbMATH DE number 2080220
• scientific article; zbMATH DE number 2086936
• On-line resource management with application to routing and scheduling
• On-line resource management with applications to routing and scheduling

Cited in

(33)

• Approximate solution of a resource-constrained scheduling problem
• Online real-time preemptive scheduling of jobs with deadlines on multiple machines
• Assessing the resource usage in scheduling with incompatibilities
• Splittable traffic partition in WDM/SONET rings to minimize SONET ADMs
• Improved algorithms for resource allocation under varying capacity
• Approximation algorithms for NMR spectral peak assignment.
• Flexible resource allocation to interval jobs
• Fair on-line scheduling of a dynamic set of tasks on a single resource
• Online optimization of busy time on parallel machines. (Extended abstract)
• Improved algorithms for resource allocation under varying capacity
• Primal-dual approximation algorithms for a packing-covering pair of problems
• Online Algorithms to Minimize Resource Reallocations and Network Communication
• On Lagrangian Relaxation and Subset Selection Problems
• A bandwidth allocation scheme for compositional real-time systems with periodic resources
• scientific article; zbMATH DE number 2080220 (Why is no real title available?)
• A new approximation technique for resource-allocation problems
• On-line resource management with applications to routing and scheduling
• scientific article; zbMATH DE number 2086936 (Why is no real title available?)
• Shape rectangularization problems in intensity-modulated radiation therapy
• On centralized smooth scheduling
• Algorithms and Computation
• A unified approach to approximating resource allocation and scheduling
• New results on web caching with request reordering
• scientific article; zbMATH DE number 7765383 (Why is no real title available?)
• Closing the gap: minimum space optimal time distance labeling scheme for interval graphs
• Caching is hard -- even in the fault model
• Unsplittable flow on a short path
• Efficient job scheduling algorithms with multi-type contentions
• Resource scheduling with variable requirements over time
• Approximation algorithm for periodic real-time tasks with workload-dependent running-time functions
• Real-time scheduling to minimize machine busy times
• Improved approximation algorithm for convex recoloring of trees
• Bicriteria scheduling for contiguous and non contiguous parallel tasks

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5895207)