265 citations · 441 across the 39 of their papers we have counts for
20 papers · 1 filter
Optimal Online Discrepancy Minimization
Janardhan Kulkarni, Victor Reis, Thomas Rothvoss
We prove that there exists an online algorithm that for any sequence of vectors with , arriving one at a time, decides random si…
Online Edge Coloring via Tree Recurrences and Correlation Decay
Janardhan Kulkarni, Yang P. Liu, Ashwin Sah +2
We give an online algorithm that with high probability computes a edge coloring on a graph with maximum degree under online…
On the Hardness of Scheduling With Non-Uniform Communication Delays
Sami Davies, Janardhan Kulkarni, Thomas Rothvoss +3
In the scheduling with non-uniform communication delay problem, the input is a set of jobs with precedence constraints. Associated with every precedence constraint between a pair o…
Consistent -Median: Simpler, Better and Robust
Xiangyu Guo, Janardhan Kulkarni, Shi Li +1
In this paper we introduce and study the online consistent -clustering with outliers problem, generalizing the non-outlier version of the problem studied in [Lattanzi-Vassilvits…
Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints
Janardhan Kulkarni, Shi Li, Jakub Tarnawski +1
We consider the classic problem of scheduling jobs with precedence constraints on a set of identical machines to minimize the makespan objective function. Understanding the exact a…
Scheduling with Communication Delays via LP Hierarchies and Clustering
Sami Davies, Janardhan Kulkarni, Thomas Rothvoss +2
We consider the classic problem of scheduling jobs with precedence constraints on identical machines to minimize makespan, in the presence of communication delays. In this setting,…
The Power of Recourse: Better Algorithms for Facility Location in Online and Dynamic Models
Xiangyu Guo, Janardhan Kulkarni, Shi Li +1
In this paper we study the facility location problem in the online with recourse and dynamic algorithm models. In the online with recourse model, clients arrive one by one and our…
Locally Private Hypothesis Selection
Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni +3
We initiate the study of hypothesis selection under local differential privacy. Given samples from an unknown probability distribution and a set of probability distribution…
Privately Learning Markov Random Fields
Huanyu Zhang, Gautam Kamath, Janardhan Kulkarni +1
We consider the problem of learning Markov Random Fields (including the prototypical example, the Ising model) under the constraint of differential privacy. Our learning goals incl…
Fully Dynamic -Coloring in Constant Update Time
Sayan Bhattacharya, Fabrizio Grandoni, Janardhan Kulkarni +2
The problem of (vertex) -coloring a graph of maximum degree has been extremely well-studied over the years in various settings and models. Surprisingly, for the dynamic…
Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization
Haotian Jiang, Janardhan Kulkarni, Sahil Singla
Consider a unit interval in which points arrive one-by-one independently and uniformly at random. On arrival of a point, the problem is to immediately and irrevocably c…
Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
David Durfee, Laxman Dhulipala, Janardhan Kulkarni +3
In this paper we study the problem of dynamically maintaining graph properties under batches of edge insertions and deletions in the massively parallel model of computation. In thi…
An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs
Sayan Bhattacharya, Janardhan Kulkarni
We consider the problem of incremental cycle detection and topological ordering in a directed graph with nodes. In this setting, initially the edge-set o…
A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time
Uriel Feige, Janardhan Kulkarni, Shi Li
We consider the classic scheduling problem of minimizing the total weighted flow-time on a single machine (min-WPFT), when preemption is allowed. In this problem, we are given a se…
Flow-time Optimization For Concurrent Open-Shop and Precedence Constrained Scheduling Models
Janardhan Kulkarni, Shi Li
Scheduling a set of jobs over a collection of machines is a fundamental problem that needs to be solved millions of times a day in various computing platforms: in operating systems…
Deterministically Maintaining a -Approximate Minimum Vertex Cover in Amortized Update Time
Sayan Bhattacharya, Janardhan Kulkarni
We consider the problem of maintaining an (approximately) minimum vertex cover in an -node graph that is getting updated dynamically via a sequence of edge insertio…
Tight Bounds for Online Vector Scheduling
Sungjin Im, Nathaniel Kell, Janardhan Kulkarni +1
Modern data centers face a key challenge of effectively serving user requests that arrive online. Such requests are inherently multi-dimensional and characterized by demand vectors…
SELFISHMIGRATE: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors
Sungjin Im, Janardhan Kulkarni, Kamesh Munagala +1
We consider the classical problem of minimizing the total weighted flow-time for unrelated machines in the online \emph{non-clairvoyant} setting. In this problem, a set of jobs …
Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraints
Sungjin Im, Janardhan Kulkarni, Kamesh Munagala
We introduce and study a general scheduling problem that we term the Packing Scheduling problem. In this problem, jobs can have different arrival times and sizes; a scheduler can p…
Minimizing Flow-Time on Unrelated Machines
Nikhil Bansal, Janardhan Kulkarni
We consider some flow-time minimization problems in the unrelated machines setting. In this setting, there is a set of machines and a set of jobs, and each job has a ma…