2 citations · 4 across the 8 of their papers we have counts for
7 papers · 1 filter
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, ...…
Non-clairvoyant Precedence Constrained Scheduling
Naveen Garg, Anupam Gupta, Amit Kumar +1
We consider the online problem of scheduling jobs on identical machines, where jobs have precedence constraints. We are interested in the demanding setting where the jobs sizes are…
Tight FPT Approximations for -Median and -Means
Vincent Cohen-Addad, Anupam Gupta, Amit Kumar +2
We investigate the fine-grained complexity of approximating the classical -median / -means clustering problems in general metric spaces. We show how to improve the approximat…
Reoptimization of Path Vertex Cover Problem
Mehul Kumar, Amit Kumar, C. Pandu Rangan
Most optimization problems are notoriously hard. Considerable efforts must be spent in obtaining an optimal solution to certain instances that we encounter in the real world scenar…