33 citations · 122 across the 14 of their papers we have counts for
15 papers · 1 filter
Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse
Ravishankar Krishnaswamy, Shi Li, Varun Suriyanarayana
We consider the online unrelated-machine load balancing problem with recourse, where the algorithm is allowed to re-assign prior jobs. We give a -competitive algorithm for t…
Online Discrepancy with Recourse for Vectors and Graphs
Anupam Gupta, Vijaykrishna Gurunathan, Ravishankar Krishnaswamy +2
The vector-balancing problem is a fundamental problem in discrepancy theory: given T vectors in , find a signing of each vector to minimize the d…
Online Carpooling using Expander Decompositions
Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar +1
We consider the online carpooling problem: given vertices, a sequence of edges arrive over time. When an edge arrives at time step , the algorithm must or…
PERMUTATION Strikes Back: The Power of Recourse in Online Metric Matching
Varun Gupta, Ravishankar Krishnaswamy, Sai Sandeep
In the classical Online Metric Matching problem, we are given a metric space with servers. A collection of clients arrive in an online fashion, and upon arrival, a client shoul…
Constant Approximation for -Median and -Means with Outliers via Iterative Rounding
Ravishankar Krishnaswamy, Shi Li, Sai Sandeep
In this paper, we present a new iterative rounding framework for many clustering problems. Using this, we obtain an -approximation algorithm for -median…
The Heterogeneous Capacitated -Center Problem
Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Amit Kumar
In this paper we initiate the study of the heterogeneous capacitated -center problem: given a metric space , and a collection of capacities. The goal is to op…