22 citations · 38 across the 14 of their papers we have counts for
24 papers
A General Framework for Matching with Delays
Sara Ahmadian, Shuchi Chawla, Ravi Kumar +2
We present a simple deterministic -competitive algorithm for the online minimum-cost perfect matching with delays (MPMD) problem on arbitrary, unknown metric spaces, whe…
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…
Optimizing Memory Mapping Using Deep Reinforcement Learning
Pengming Wang, Mikita Sazanovich, Berkin Ilbeyi +16
Resource scheduling and allocation is a critical component of many high impact systems ranging from congestion control to cloud computing. Finding more optimal solutions to these p…
Caching with Reserves
Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina +2
Caching is a crucial component of many computer systems, so naturally it is a well-studied topic in algorithm design. Much of traditional caching research studies cache management…
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…
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…
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…
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-…
Upper Confidence Bounds for Combining Stochastic Bandits
Ashok Cutkosky, Abhimanyu Das, Manish Purohit
We provide a simple method to combine stochastic bandit algorithms. Our approach is based on a "meta-UCB" procedure that treats each of individual bandit algorithms as arms in…
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…
Strategy-proof and Envy-free Mechanisms for House Allocation
Priyanka Shende, Manish Purohit
We consider the problem of allocating indivisible objects to agents when agents have strict preferences over objects. There are inherent trade-offs between competing notions of eff…
Online Linear Optimization with Many Hints
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar +1
We study an online linear optimization (OLO) problem in which the learner is provided access to "hint" vectors in each round prior to making a decision. In this setting, we dev…
Online Learning with Imperfect Hints
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar +1
We consider a variant of the classical online linear optimization problem in which at every step, the online player receives a "hint" vector before choosing the action for that rou…
Near Optimal Coflow Scheduling in Networks
Mosharaf Chowdhury, Samir Khuller, Manish Purohit +2
The coflow scheduling problem has emerged as a popular abstraction in the last few years to study data communication problems within a data center. In this basic framework, each co…
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…
Semi-Online Bipartite Matching
Ravi Kumar, Manish Purohit, Aaron Schild +2
In this paper we introduce the \emph{semi-online} model that generalizes the classical online computational model. The semi-online model postulates that the unknown future has a pr…
A Tight Approximation for Co-flow Scheduling for Minimizing Total Weighted Completion Time
Sungjin Im, Manish Purohit
Co-flows model a modern scheduling setting that is commonly found in a variety of applications in distributed and cloud computing. In co-flow scheduling, there are input ports…
On Correcting Inputs: Inverse Optimization for Online Structured Prediction
Hal Daumé, Samir Khuller, Manish Purohit +1
Algorithm designers typically assume that the input data is correct, and then proceed to find "optimal" or "sub-optimal" solutions using this input data. However this assumption of…
On the Approximability of Digraph Ordering
Sreyash Kenkre, Vinayaka Pandit, Manish Purohit +1
Given an n-vertex digraph D = (V, A) the Max-k-Ordering problem is to compute a labeling maximizing the number of forward edges, i.e. edges (u,v) such that $\ell…
Approximation Algorithms for Connected Maximum Cut and Related Problems
MohammadTaghi Hajiaghayi, Guy Kortsarz, Robert MacDavid +2
An instance of the Connected Maximum Cut problem consists of an undirected graph G = (V, E) and the goal is to find a subset of vertices S V that maximizes the number o…
Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems
Samir Khuller, Manish Purohit, Kanthi Sarpatwar
We study partial and budgeted versions of the well studied connected dominating set problem. In the partial connected dominating set problem, we are given an undirected graph G = (…
Improved algorithms and analysis for the laminar matroid secretary problem
David Harris, Manish Purohit
In a matroid secretary problem, one is presented with a sequence of objects of various weights in a random order, and must choose irrevocably to accept or reject each item. There i…