Research

My research lies broadly in the areas of algorithms and optimization. Most real-life optimization problems are computationally hard in nature and heuristic algorithms are employed in most applications. Although these heuristics are time efficient and work well for some inputs, they cannot assure good quality solutions on every input instance. To address this issue, researchers design approximation algorithms, which guarantee good bounds on the quality of the solutions on all inputs. Many problems have the nature that they are not only hard to solve optimally, but also hard to approximate even if we could afford to use any reasonable amount of time. Accordingly, my research philosophy is to explore the solvability of such problems in terms of approximation. One of my focus research topics is algorithmic fairness, where the goal is to design algorithms that are fair for all participating groups. Following are some topics of my interest. 

• Clustering and covering problems, facility location

• Algorithmic fairness

• Low-rank approximation and dimensionality reduction

• Capacitated set cover

• Approximability of NP-hard problems

• Fixed-parameter Tractability

(The percentages beside the publications denote the acceptance rate)

2024

• Constant-Approximation Algorithms for Fair Sum-of-Radii Clustering with Sina Bagheri Nezhad, Sayan Bandyapadhyay, Tianzhi Chen draft

• A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering with Sayan Bandyapadhyay, Eden Chlamtac, Yury Makarychev, Ali Vakilian arXiv

• An O(n log⁡n)-Time Approximation Scheme for Geometric Many-to-Many Matching with Jie Xue SoCG (83/235 ~ 35%) (Recipient of Best Paper Award)

• Geometric Covering via Extraction Theorem with Anil Maheshwari, Sasanka Roy, Michiel Smid, Kasturi Varadarajan ITCS Talk

• Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable with William Lochet, Daniel Lokshtanov, Saket Saurabh, Jie Xue SODA

2023

• Coresets for Clustering in Geometric Intersection Graphs  with Fedor V. Fomin, Tanmay Inamdar SoCG arXiv (61/175 = 34%)

• FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii  with William Lochet, Saket Saurabh SoCG arXiv (61/175 = 34%)

• Minimum-Membership Geometric Set Cover, Revisited  with William Lochet, Saket Saurabh, Jie Xue SoCG (61/175 = 34%)

•  Socially Fair Matching: Exact and Approximation Algorithms with Fedor V. Fomin, Tanmay Inamdar, Fahad Panolan, Kirill Simonov WADS

• A Parameterized Approximation Scheme for Generalized Partial Vertex Cover with Zachary Friggstad and Ramin Mousavi  WADS 

• Proportionally Fair Matching with Multiple Groups  with Fedor V. Fomin, Tanmay Inamdar, Kirill Simonov arxiv accepted WG

2022

• True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs  with William Lochet, Daniel Lokshtanov, Saket Saurabh, Jie Xue SoCG (64/174 = 36%) 

• Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs with William Lochet, Daniel Lokshtanov, Saket Saurabh, Jie Xue SODA arxiv 

• How to Find a Good Explanation for Clustering? with Fedor V. Fomin, Petr A. Golovach, William Lochet, Nidhi Purohit, Kirill Simonov AAAI arxiv Journal of AI

• Parameterized Approximation Algorithms for k-Center Clustering and Variants with Zachary Friggstad and Ramin Mousavi  AAAI arxiv Algorithmica

• Lossy Kernelization of Same-Size Clustering with Fedor V. Fomin, Petr A. Golovach, Nidhi Purohit, Kirill Simonov CSR arxiv ToCS-Journal

• FPT Approximation for Fair Minimum-Load Clustering with Fedor V. Fomin, Petr A. Golovach, Nidhi Purohit, Kirill Simonov arxiv, IPEC

2021

• Exact and Approximation Algorithms for Many-To-Many Point Matching in the Plane with Anil Maheshwari, Michiel Smid ISAAC arxiv

• On Fair Covering and Hitting Problems with Aritra Banik, Sujoy Bhore WG Algorithmica

• On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications with Fedor V. Fomin, Kirill Simonov  arxiv   ICALP   JCSS

• Parameterized Complexity of Robust Categorical Data Clustering with Fedor V. Fomin, Petr A. Golovach, Kirill Simonov arxiv  MFCS ACM ToCT-Journal

2020

• Improved Bounds for Metric Capacitated Covering Problems ESA Algorithmica Journal

• On Perturbation Resilience of Non-Uniform k-Center APPROX   Algorithmica Journal

• Geometric Planar Networks on Bichromatic Points with Aritra Banik, Sujoy Bhore, Martin Nöllenburg  CALDAM TCS-Journal 

2019

• A Constant Approximation for Colorful k-Center with Tanmay Inamdar, Shreyas Pai and Kasturi Varadarajan ESA, arxiv

• Constrained Orthogonal Segment Stabbing with Saeed Mehrabi CCCG, arxiv

2018

• Improved Approximation Bounds for the Minimum Constraint Removal Problem with Neeraj Kumar, Subhash Suri and Kasturi Varadarajan APPROX (28/50=56%), CGTA

• Approximating Dominating Set on Intersection Graphs of L-frames with Anil Maheshwari, Saeed Mehrabi and Subhash Suri MFCS (84/212=40%), arxiv, CGTA

• Capacitated Covering Problems in Geometric Spaces with Santanu Bhowmick, Tanmay Inamdar and Kasturi Varadarajan SoCG (73/206=35%), arxiv, DCG (special issue)

• Near Optimal Clustering in k-machine model with Tanmay Inamdar, Shreyas Pai and Sriram V. Pemmaraju, ICDCN (18/36=50%) TCS-Journal

2017

• Effectiveness of Local Search for Art Gallery Problems with Aniket Basu Roy, WADS (49/109=45%)

• Polynomial Time Algorithms for Bichromatic Problems with Aritra Banik, CALDAM (32/103=31%) arxiv

2016

• Approximate Clustering via Metric Partitioning with Kasturi Varadarajan, ISAAC (62/155=40%), arxiv

• On Variants of k-means Clustering with Kasturi Varadarajan, SoCG (61/160=38%)

2015

• On the Approximability of Orthogonal Order Preserving Layout Adjustment with Santanu Bhowmick and Kasturi Varadarajan, WADS (51/148=34%), Full version

• Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation with Santanu Bhowmick and Kasturi Varadarajan, SODA (137/495=27%), arxiv 

• Voronoi Game on Graphs with Aritra Banik, Sandip Das and Hirak Sarkar, WALCOM (29/86=33%), arxiv, TCS Journal 2015

Technical Reports

• Digging Deeper into Clustering and Covering Problems, PhD Thesis, pdf 

• Cover Decomposability of Convex Polygons and Octants, PhD Qualifier Report, pdf

• Voronoi Game on Graphs, Master's Thesis, pdf

• A Constant Approximation for Streaming k-means pdf (term paper)

• A Variant of the Maximum Weight Independent Set Problem, arxiv

DBLP, Google Scholar

• AAAI 2023, CALDAM 2024, SoCG 2024

• Conferences: SODA 2024, WADS 2023, STOC 2023, SoCG 2022, CALDAM 2022, FSTTCS 2021, ISAAC 2021, SoCG 2021, WADS 2021, STOC 2021, STACS 2021, CALDAM 2021, SOSA 2021, SODA 2021, STACS 2020, CALDAM 2020, WADS 2019, WG 2019, SoCG 2018, WALCOM 2018, STACS 2017, ESA 2016 

• Journals: Computational Geometry: Theory and Applications, Information Processing Letters, Mathematical Programming, Theoretical Computer Science, Algorithmica, International Journal of Computational Geometry and Applications