BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Ragesh Jaiswal contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We give an $O^*(1.0821^n)$-time, polynomial space algorithm for computing Maximum Independent Set in graphs with bounded degree 3. This improves all the previous running time bounds known for the problem.
The Metric $k$-median problem over a metric space $(\mathcal{X}, d)$ is defined as follows: given a set $L \subseteq \mathcal{X}$ of facility locations and a set $C \subseteq \mathcal{X}$ of clients, open a set $F \subseteq L$ of $k$ facilities such that the total service cost, defined as $Φ(F, C) \equiv \sum_{x \in C} \min_{f \in F} d(x, f)$, is minimised. The metric $k$-means problem is defined similarly using squared distances. In many applications there are additional constraints that any solution needs to satisfy. This gives rise to different constrained versions of the problem such as $r$-gather, fault-tolerant, outlier $k$-means/$k$-median problem. Surprisingly, for many of these constrained problems, no constant-approximation algorithm is known. We give FPT algorithms with constant approximation guarantee for a range of constrained $k$-median/means problems. For some of the constrained problems, ours is the first constant factor approximation algorithm whereas for others, we improve or match the approximation guarantee of previous works. We work within the unified framework of Ding and Xu that allows us to simultaneously obtain algorithms for a range of constrained problems. In particular, we obtain a $(3+\varepsilon)$-approximation and $(9+\varepsilon)$-approximation for the constrained versions of the $k$-median and $k$-means problem respectively in FPT time. In many practical settings of the $k$-median/means problem, one is allowed to open a facility at any client location, i.e., $C \subseteq L$. For this special case, our algorithm gives a $(2+\varepsilon)$-approximation and $(4+\varepsilon)$-approximation for the constrained versions of $k$-median and $k$-means problem respectively in FPT time. Since our algorithm is based on simple sampling technique, it can also be converted to a constant-pass log-space streaming algorithm.
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, ..., X_k$ of the dataset $X \subseteq \mathbb{R}^d$, find a list of $k$-center sets (each element in the list is a set of $k$ centers) such that at least one of $k$-center sets $\{c_1, ..., c_k\}$ in the list gives an $(1+\varepsilon)$-approximation with respect to the cost function $\min_{\textrm{permutation } π} \left[ \sum_{i=1}^{k} \sum_{x \in X_i} ||x - c_{π(i)}||^2 \right]$. The list-$k$-means problem is important for the constrained $k$-means problem since algorithms for the former can be converted to PTAS for various versions of the latter. Following are the consequences of our generalisations: - Streaming algorithm: Our $D^2$-sampling based algorithm running in a single iteration allows us to design a 2-pass, logspace streaming algorithm for the list-$k$-means problem. This can be converted to a 4-pass, logspace streaming PTAS for various constrained versions of the $k$-means problem. - Faster PTAS under stability: Our generalisation is also useful in $k$-means clustering scenarios where finding good centers becomes easy once good centers for a few "bad" clusters have been chosen. One such scenario is clustering under stability where the number of such bad clusters is a constant. Using the above idea, we significantly improve the running time of the known algorithm from $O(dn^3) (k \log{n})^{poly(\frac{1}β, \frac{1}{\varepsilon})}$ to $O \left(dn^3 k^{\tilde{O}_{β\varepsilon}(\frac{1}{β\varepsilon})} \right)$.