22 citations · 34 across the 8 of their papers we have counts for
9 papers · 1 filter
Multi-Level Aggregation via Dual Fitting: An -Competitive Algorithm
Sara Ahmadian, Shuchi Chawla, Ravi Kumar +2
We present a new online algorithm for the well-known Multi-Level Aggregation Problem (MLAP) with arbitrary delay functions, achieving a -competitive ratio, where is the dep…
Online Load and Graph Balancing for Random Order Inputs
Sungjin Im, Ravi Kumar, Shi Li +2
Online load balancing for heterogeneous machines aims to minimize the makespan (maximum machine workload) by scheduling arriving jobs with varying sizes on different machines. In t…
Efficient Caching with Reserves via Marking
Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina +2
Online caching is among the most fundamental and well-studied problems in the area of online algorithms. Innovative algorithmic ideas and analysis -- including potential functions…
Parsimonious Learning-Augmented Caching
Sungjin Im, Ravi Kumar, Aditya Petety +1
Learning-augmented algorithms -- in which, traditional algorithms are augmented with machine-learned predictions -- have emerged as a framework to go beyond worst-case analysis. Th…
Learning-Augmented Weighted Paging
Nikhil Bansal, Christian Coester, Ravi Kumar +2
We consider a natural semi-online model for weighted paging, where at any time the algorithm is given predictions, possibly with errors, about the next arrival of each page. The mo…
Hiring Under Uncertainty
Manish Raghavan, Manish Purohit, Sreenivas Gollupadi
In this paper we introduce the hiring under uncertainty problem to model the questions faced by hiring committees in large enterprises and universities alike. Given a set of el…