Neelima Gupta
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Neelima Gupta has a total of 27 co-authors. Here are the top co-authors by number of shared publications:
- Rajni Dabas
Department of Computer Science, University of Delhi, Delhi, India
7 shared publications - Sapna Grover
Dyal Singh College, University of Delhi, IN
4 shared publications - Naveen Garg
Indian Institute of Technology Delhi
3 shared publications - Aditya Pancholi
Department of Computer Science, University of Delhi
2 shared publications - Sandhya Aneja
School of Computer Science and Mathematics, Marist College, Poughkeepsie, NY, USA
2 shared publications - Sanjay Madria
Missouri University of Science and Technology
2 shared publications
Latest Publications
- 8 February 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1069
Respecting lower bounds in uniform lower and upper bounded facility location problem
- 8 February 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1069
Respecting lower bounds in uniform lower and upper bounded facility location problem
- 17 July 2025
- Published by Springer Nature in Mathematical Programming
- Vol. 216 (1-2) , 275-294
Capacitated facility location with outliers and uniform facility costs
- 17 July 2025
- Published by Springer Nature in Mathematical Programming
- Vol. 216 (1-2) , 275-294
Capacitated facility location with outliers and uniform facility costs
- 24 January 2025
- Published by Elsevier in Discrete Optimization
- Vol. 55
Uniform capacitated facility location with outliers/penalties
- 24 January 2025
- Published by Elsevier in Discrete Optimization
- Vol. 55
Uniform capacitated facility location with outliers/penalties
- 22 May 2024
- Published by Springer Nature
- p. 85-98
Capacitated Facility Location with Outliers and Uniform Facility Costs
- 22 May 2024
- Published by Springer Nature
- p. 85-98
Capacitated Facility Location with Outliers and Uniform Facility Costs
- Open Access
- 21 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 386-397
Scalable algorithms for compact spanners on real world graphs
A graph spanner is a subgraph that preserves the shortest distance between every pair of vertices within a permissible distortion. Typically, the allowed distortion is a multiplicative factor (of the original distances) and is referred to as stretch. Efficient multiplicative spanners, based on finding low diameter decompositions, have been studied in the distributed and parallel settings. Most of these studies aim to find spanners with theoretical guarantees on the stretch and spanner size. The spanner size guarantees obtained in these works are not very useful for real world sparse graphs. In this work, we evaluate and compare the state of the art algorithms for multiplicative spanners on real world and synthetic graphs. We propose a heuristic that aims to reduce the size of the output spanner. When combined with existing approaches, it admits similar theoretical guarantees as described in prior work while yielding considerably smaller spanners. Our heuristic builds on the idea of selecting centers with large neighborhoods and growing clusters around them. We present a parallel algorithm for selecting a large set of cluster centers based on this heuristic. We evaluate our algorithms on 18 real world graphs from the SNAP data set and 3 well studied synthetic graphs. We demonstrate that our heuristic yields spanners with significantly fewer edges - up to 6x smaller on real world graphs and up to 20x smaller on synthetic graphs, compared to baselines from prior work.
- 21 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 386-397
Open AccessScalable algorithms for compact spanners on real world graphs
A graph spanner is a subgraph that preserves the shortest distance between every pair of vertices within a permissible distortion. Typically, the allowed distortion is a multiplicative factor (of the original distances) and is referred to as stretch. Efficient multiplicative spanners, based on finding low diameter decompositions, have been studied in the distributed and parallel settings. Most of these studies aim to find spanners with theoretical guarantees on the stretch and spanner size. The spanner size guarantees obtained in these works are not very useful for real world sparse graphs. In this work, we evaluate and compare the state of the art algorithms for multiplicative spanners on real world and synthetic graphs. We propose a heuristic that aims to reduce the size of the output spanner. When combined with existing approaches, it admits similar theoretical guarantees as described in prior work while yielding considerably smaller spanners. Our heuristic builds on the idea of selecting centers with large neighborhoods and growing clusters around them. We present a parallel algorithm for selecting a large set of cluster centers based on this heuristic. We evaluate our algorithms on 18 real world graphs from the SNAP data set and 3 well studied synthetic graphs. We demonstrate that our heuristic yields spanners with significantly fewer edges - up to 6x smaller on real world graphs and up to 20x smaller on synthetic graphs, compared to baselines from prior work.
- Open Access
FPT Approximations for Capacitated/Fair Clustering with Outliers
Clustering problems such as $k$-Median, and $k$-Means, are motivated from applications such as location planning, unsupervised learning among others. In such applications, it is important to find the clustering of points that is not ``skewed'' in terms of the number of points, i.e., no cluster should contain too many points. This is modeled by capacity constraints on the sizes of clusters. In an orthogonal direction, another important consideration in clustering is how to handle the presence of outliers in the data. Indeed, these clustering problems have been generalized in the literature to separately handle capacity constraints and outliers. To the best of our knowledge, there has been very little work on studying the approximability of clustering problems that can simultaneously handle both capacities and outliers. We initiate the study of the Capacitated $k$-Median with Outliers (C$k$MO) problem. Here, we want to cluster all except $m$ outlier points into at most $k$ clusters, such that (i) the clusters respect the capacity constraints, and (ii) the cost of clustering, defined as the sum of distances of each non-outlier point to its assigned cluster-center, is minimized. We design the first constant-factor approximation algorithms for C$k$MO. In particular, our algorithm returns a (3+ε)-approximation for C$k$MO in general metric spaces, and a (1+ε)-approximation in Euclidean spaces of constant dimension, that runs in time in time $f(k, m, ε) \cdot |I_m|^{O(1)}$, where $|I_m|$ denotes the input size. We can also extend these results to a broader class of problems, including Capacitated k-Means/k-Facility Location with Outliers, and Size-Balanced Fair Clustering problems with Outliers. For each of these problems, we obtain an approximation ratio that matches the best known guarantee of the corresponding outlier-free problem.Open AccessFPT Approximations for Capacitated/Fair Clustering with Outliers
Clustering problems such as $k$-Median, and $k$-Means, are motivated from applications such as location planning, unsupervised learning among others. In such applications, it is important to find the clustering of points that is not ``skewed'' in terms of the number of points, i.e., no cluster should contain too many points. This is modeled by capacity constraints on the sizes of clusters. In an orthogonal direction, another important consideration in clustering is how to handle the presence of outliers in the data. Indeed, these clustering problems have been generalized in the literature to separately handle capacity constraints and outliers. To the best of our knowledge, there has been very little work on studying the approximability of clustering problems that can simultaneously handle both capacities and outliers. We initiate the study of the Capacitated $k$-Median with Outliers (C$k$MO) problem. Here, we want to cluster all except $m$ outlier points into at most $k$ clusters, such that (i) the clusters respect the capacity constraints, and (ii) the cost of clustering, defined as the sum of distances of each non-outlier point to its assigned cluster-center, is minimized. We design the first constant-factor approximation algorithms for C$k$MO. In particular, our algorithm returns a (3+ε)-approximation for C$k$MO in general metric spaces, and a (1+ε)-approximation in Euclidean spaces of constant dimension, that runs in time in time $f(k, m, ε) \cdot |I_m|^{O(1)}$, where $|I_m|$ denotes the input size. We can also extend these results to a broader class of problems, including Capacitated k-Means/k-Facility Location with Outliers, and Size-Balanced Fair Clustering problems with Outliers. For each of these problems, we obtain an approximation ratio that matches the best known guarantee of the corresponding outlier-free problem. - 21 October 2022
- Published by Springer Nature
- p. 1-19
Locating Service and Charging Stations
- 2 June 2022
- Published by Elsevier in Discrete Optimization
- Vol. 45
LP-based approximation for uniform capacitated facility location problem
- 2 June 2022
- Published by Elsevier in Discrete Optimization
- Vol. 45
LP-based approximation for uniform capacitated facility location problem
- 1 January 2022
- Published by Springer Nature
- p. 549-560
Capacitated Facility Location with Outliers/Penalties
- 1 January 2022
- Published by Springer Nature
- p. 549-560
Capacitated Facility Location with Outliers/Penalties