2 citations · 4 across the 6 of their papers we have counts for
12 papers · 1 filter
FPT Approximation for Constrained Metric -Median/Means
Dishant Goyal, Ragesh Jaiswal, Amit Kumar
The Metric -median problem over a metric space is defined as follows: given a set of facility locations and a set $C \subseteq \math…
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…
Caching with Time Windows and Delays
Anupam Gupta, Amit Kumar, Debmalya Panigrahi
We consider two generalizations of the classical weighted paging problem that incorporate the notion of delayed service of page requests. The first is the (weighted) Paging with Ti…
Multiplicative Rank-1 Approximation using Length-Squared Sampling
Ragesh Jaiswal, Amit Kumar
We show that the span of rows of any matrix sampled according to the length-squared distribution contains a rank-$1…
Streaming PTAS for Binary -Low Rank Approximation
Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal +1
We give a 3-pass, polylog-space streaming PTAS for the constrained binary -means problem and a 4-pass, polylog-space streaming PTAS for the binary -low rank approximatio…
Streaming PTAS for Constrained k-Means
Dishant Goyal, Ragesh Jaiswal, Amit Kumar
We generalise the results of Bhattacharya et al. (Journal of Computing Systems, 62(1):93-115, 2018) for the list--means problem defined as -- for a (unknown) partition $X_1, ...…