22 citations · 35 across the 11 of their papers we have counts for
Showing 2021Show all
3 papers · 1 filter
cs.CC2021
NP-completeness of the Active Time Scheduling Problem
Sagnik Saha, Manish Purohit
In this paper, we study the active time scheduling problem. We are given n jobs with integral processing times each of which has an integral release time and deadline. The goal is…
cs.LG2021
Logarithmic Regret from Sublinear Hints
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar +1
We consider the online linear optimization problem, where at every step the algorithm plays a point in the unit ball, and suffers loss for some cost…
cs.DS2021
Scheduling with Communication Delay in Near-Linear Time
Quanquan C. Liu, Manish Purohit, Zoya Svitkina +2
We consider the problem of efficiently scheduling jobs with precedence constraints on a set of identical machines in the presence of a uniform communication delay. Such precedence-…