Scheduling with gaps: new models and algorithms
From MaRDI portal
Publication:2059088
DOI10.1007/s10951-021-00691-wzbMath1479.90083MaRDI QIDQ2059088
Marek Chrobak, Mordecai J. Golin, Dorian Nogneng, Tak-Wah Lam
Publication date: 13 December 2021
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10951-021-00691-w
68Q25: Analysis of algorithms and problem complexity
90B35: Deterministic scheduling theory in operations research
90C39: Dynamic programming
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Refined algorithms for hitting many intervals
- Low complexity scheduling algorithms minimizing the energy for tasks with agreeable deadlines
- Efficient algorithms for the one-dimensional \(k\)-center problem
- Selection in \(X+Y\) and matrices with sorted rows and columns
- Geometric applications of a matrix-searching algorithm
- The complexity of selection and ranking in X+Y and matrices with sorted columns
- Improved complexity bounds for location problems on the real line
- Monge strikes again: Optimal placement of web proxies in the internet
- Perspectives of Monge properties in optimization
- A greedy approximation algorithm for minimum-gap scheduling
- Scheduling to minimize gaps and power consumption
- Low Complexity Scheduling Algorithm Minimizing the Energy for Tasks with Agreeable Deadlines
- The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity
- Polynomial-time algorithms for minimum energy scheduling
- Generalized Selection and Ranking: Sorted Matrices
- Polynomial Time Algorithms for Minimum Energy Scheduling
- Scheduling unit tasks to minimize the number of idle periods
- New Results on the Complexity of p-Centre Problems
- The disjoint cliques problem
- A Greedy Approximation Algorithm for Minimum-Gap Scheduling
- A Dynamic Programming Approach to Length-Limited Huffman Coding: Space Reduction With the Monge Property