Dishant Goyal

collaborators

3 papers

cs.DS2020

FPT Approximation for Constrained Metric $k$ -Median/Means

Dishant Goyal, Ragesh Jaiswal, Amit Kumar

The Metric $k$ -median problem over a metric space $(X, d)$ is defined as follows: given a set $L \subseteq X$ of facility locations and a set $C \subseteq \math…

cs.DS2019

Streaming PTAS for Binary $ℓ_{0}$ -Low Rank Approximation

Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal +1

We give a 3-pass, polylog-space streaming PTAS for the constrained binary $k$ -means problem and a 4-pass, polylog-space streaming PTAS for the binary $ℓ_{0}$ -low rank approximatio…

cs.DS2019

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- $k$ -means problem defined as -- for a (unknown) partition $X_1, ...…

FPT Approximation for Constrained Metric k-Median/Means

Streaming PTAS for Binary ℓ0​-Low Rank Approximation

Streaming PTAS for Constrained k-Means

FPT Approximation for Constrained Metric $k$ -Median/Means

Streaming PTAS for Binary $ℓ_{0}$ -Low Rank Approximation