5 papers
Maximum-Width Rainbow-Bisecting Empty Annulus
Sang Won Bae, Sandip Banerjee, Arpita Baral +2
Given a set of colored points with colors in the plane, we study the problem of computing a maximum-width rainbow-bisecting empty annulus (of objects specifically axis-para…
Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
Fateme Abbasi, Sandip Banerjee, Jarosław Byrka +6
We consider the well-studied Robust -Clustering problem, which generalizes the classic -Median, -Means, and -Center problems. Given a constant , the input…
Parameterized Approximation Schemes for Clustering with General Norm Objectives
Fateme Abbasi, Sandip Banerjee, Jarosław Byrka +6
This paper considers the well-studied algorithmic regime of designing a -approximation algorithm for a -clustering problem that runs in time (sometimes ca…
Min-Sum Clustering (with Outliers)
Sandip Banerjee, Rafail Ostrovsky, Yuval Rabani
We give a constant factor polynomial time pseudo-approximation algorithm for min-sum clustering with or without outliers. The algorithm is allowed to exclude an arbitrarily small c…
Algorithm and Hardness results on Liar's Dominating Set and -tuple Dominating Set
Sandip Banerjee, Sujoy Bhore
Given a graph , the dominating set problem asks for a minimum subset of vertices such that every vertex is adjacent to at least one vert…