arXiv preprint ·
Busy Time Minimization with Preemption, Migration, and One Resource Requirement
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study the Busy Machine Time with Preemption and Migration and One Resource Requirement problem, motivated by energy minimization in cloud data centers. Given unlimited identical-capacity machines and jobs with release times, deadlines, processing times, and resource requirements, we allow free preemption and migration at integer times and seek to minimize total machine busy time. The problem is NP-hard, and previous results consist of a 2-approximation, 2-competitive algorithm for the case of uniform heights. We obtain a 22/9 < 2.445-approximation algorithm and a 2.5-competitive online algorithm, both running in O(n^2 log n) time. Our methods are based on new non-asymptotic performance bounds for the First Fit Decreasing algorithm for Bin Packing, and a new generalization of Span Minimization, the Huge-Tiny Busy Time problem, for which we present an exact offline algorithm and an optimal (3/2)-competitive deterministic online algorithm.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria
The Inverse Lyndon Array
Union-Find with Constant-Time Deletions Across the Optimal Worst-Case Tradeoff
An Arboricity-Sensitive Algorithm for the $K_r-e$-Free Graph Sandwich Problem
Local Representatives and Shortest Completions for Next-to-Shortest Paths in Directed Graphs
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.