3 papers
cs.DS2020
Online Algorithms for Weighted Paging with Predictions
Zhihao Jiang, Debmalya Panigrahi, Kevin Sun
In this paper, we initiate the study of the weighted paging problem with predictions. This continues the recent line of work in online algorithms with predictions, particularly tha…
cs.DS2020
Sparsification of Directed Graphs via Cut Balance
Ruoxu Cen, Yu Cheng, Debmalya Panigrahi +1
In this paper, we consider the problem of designing cut sparsifiers and sketches for directed graphs. To bypass known lower bounds, we allow the sparsifier/sketch to depend on the…
cs.DS2017
Select and Permute: An Improved Online Framework for Scheduling to Minimize Weighted Completion Time
Samir Khuller, Jingling Li, Pascal Sturmfels +2
In this paper, we introduce a new online scheduling framework for minimizing total weighted completion time in a general setting. The framework is inspired by the work of Hall et a…