Dishant Goyal

activity

20192024

most citedHardness of Approximation of Euclidean

k

-Median

1 citations · 1 across the 5 of their papers we have counts for

collaborators

7 papers

cs.DS2024

Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs

Dishant Goyal, Ashwin Jacob, Kaushtubh Kumar +2

We consider structural parameterizations of the fundamental Dominating Set problem and its variants in the parameter ecology program. We give improved FPT algorithms and lower boun…

cs.DS2021

Tight FPT Approximation for Constrained k-Center and k-Supplier

Dishant Goyal, Ragesh Jaiswal

In this work, we study a range of constrained versions of the $k$ -supplier and $k$ -center problems such as: capacitated, fault-tolerant, fair, etc. These problems fall under a broa…

cs.DS2021

Tight FPT Approximation for Socially Fair Clustering

Dishant Goyal, Ragesh Jaiswal

In this work, we study the socially fair $k$ -median/ $k$ -means problem. We are given a set of points $P$ in a metric space $X$ with a distance function $d (., .)$ . There are…

cs.CC2020★ 1 cited

Hardness of Approximation of Euclidean $k$ -Median

Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal

The Euclidean $k$ -median problem is defined in the following manner: given a set $X$ of $n$ points in $R^{d}$ , and an integer $k$ , find a set $C \subset \mathbb{…

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…