11 citations · 29 across the 22 of their papers we have counts for
17 papers · 1 filter
Competitive Random-Order Correlation k-Clustering
Mahsa Derakhshan, Andisheh Ghasemi, Rajmohan Rajaraman +2
Correlation clustering has been extensively studied over the last two decades in many different computational models owing to its wide-ranging practical applications. The goal is t…
Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
Soheil Behnezhad, Rajmohan Rajaraman, Omer Wasim
Over the years, there has been extensive work on fully dynamic algorithms for classic graph problems that admit greedy solutions. Examples include vertex coloring, maximal…
Competitive Capacitated Online Recoloring
Rajmohan Rajaraman, Omer Wasim
In this paper, we revisit the online recoloring problem introduced recently by Azar et al. In online recoloring, there is a fixed set of vertices and an initial coloring $c…
Scheduling Splittable Jobs on Configurable Machines
Matthew Casey, Rajmohan Rajaraman, David Stalfa
Motivated by deep neural network applications, we study the problem of scheduling splittable jobs (e.g., neural network inference tasks) on configurable machines (e.g., multi-insta…
One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree
Costas Busch, Da Qi Chen, Arnold Filtser +3
A spanning tree of graph is a -approximate universal Steiner tree (UST) for root vertex if, for any subset of vertices containing , the cost of the minimal su…
Scheduling under Non-Uniform Job and Machine Delays
Rajmohan Rajaraman, David Stalfa, Sheng Yang
We study the problem of scheduling precedence-constrained jobs on heterogenous machines in the presence of non-uniform job and machine communication delays. We are given as input $…