research
∙
08/30/2023
On Colorful Vertex and Edge Cover Problems
In this paper, we study two generalizations of Vertex Cover and Edge Cov...
share
research
∙
05/06/2023
Minimum-Membership Geometric Set Cover, Revisited
We revisit a natural variant of geometric set cover, called minimum-memb...
research
∙
03/14/2023
FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
Clustering with capacity constraints is a fundamental problem that attra...
research
∙
03/02/2023
Coresets for Clustering in Geometric Intersection Graphs
Designing coresets–small-space sketches of the data preserving cost of t...
research
∙
01/10/2023
Proportionally Fair Matching with Multiple Groups
The study of fair algorithms has become mainstream in machine learning a...
research
∙
12/19/2021
Parameterized Approximation Algorithms for k-Center Clustering and Variants
k-center is one of the most popular clustering models. While it admits a...
research
∙
12/13/2021
How to Find a Good Explanation for Clustering?
k-means and k-median clustering are powerful unsupervised machine learni...
research
∙
11/28/2021
Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs
We design the first subexponential-time (parameterized) algorithms for s...
research
∙
09/15/2021
Exact and Approximation Algorithms for Many-To-Many Point Matching in the Plane
Given two sets S and T of points in the plane, of total size n, a many-t...
research
∙
07/20/2021
FPT Approximation for Fair Minimum-Load Clustering
In this paper, we consider the Minimum-Load k-Clustering/Facility Locati...
research
∙
07/15/2021
Lossy Kernelization of Same-Size Clustering
In this work, we study the k-median clustering problem with an additiona...
research
∙
05/08/2021
Parameterized Complexity of Feature Selection for Categorical Data Clustering
We develop new algorithmic methods with provable guarantees for feature ...
research
∙
07/22/2020
Approximate Covering with Lower and Upper Bounds via LP Rounding
In this paper, we study the lower- and upper-bounded covering (LUC) prob...
research
∙
07/20/2020
On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications
Fair clustering is a constrained variant of clustering where the goal is...
research
∙
06/22/2020
Improved Bounds for Metric Capacitated Covering Problems
In the Metric Capacitated Covering (MCC) problem, given a set of balls ℬ...
research
∙
04/27/2020
On Perturbation Resilience of Non-Uniform k-Center
The Non-Uniform k-center (NUkC) problem has recently been formulated by ...
research
∙
11/20/2019
Geometric Planar Networks on Bichromatic Points
We study four classical graph problems – Hamiltonian path, Traveling sal...
research
∙
07/21/2019
A Constant Approximation for Colorful k-Center
In this paper, we consider the colorful k-center problem, which is a gen...
research
∙
04/30/2019
Constrained Orthogonal Segment Stabbing
Let S and D each be a set of orthogonal line segments in the plane. A li...
research
∙
03/16/2018
Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames
We consider the Minimum Dominating Set (MDS) problem on the intersection...
research
∙
03/16/2018
Approximating Dominating Set on Intersection Graphs of L-frames
We consider the Dominating Set (DS) problem on the intersection graphs o...
research
∙
10/23/2017