Brief Announcement: A Greedy 2 Approximation for the Active Time Problem
Brief Announcement: A Greedy 2 Approximation for the Active Time Problem
复制标题
简短公告：活跃时间问题的贪婪 2 近似
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
S. Khuller
中科院分区：
文献类型：
--
作者：
Saurabh Kumar;S. Khuller
In this note, we give a simple 2 approximation for the active time problem - we are given a set of pre-emptible jobs, each with an integral release time, deadline and required processing length. The jobs need to be scheduled on a machine that can process at most g distinct job units at any given integral time slot, in such a way that we minimize the time the machine is on i.e the active time. Our algorithm matches the state of the art bound obtained by a significantly more involved LP rounding scheme.
