Assistant Professor (on Lien), Visiting Faculty at Northwestern University, USA | Department of Computer Science
Contact (Off.): 9650361897
Email Address : rajni[dot]dabas[at]pgdav[dot]du[dot]ac[dot]in
Theoretical Computer Science, specifically Approximation Algorithms.
Dr. Rajni is currently a Visiting Faculty at Northwestern University, on lien from her position as Assistant Professor at P.G.D.A.V. College (University of Delhi). Her role at Northwestern is primarily research-focused; she has joined Prof. Samir Khuller’s research group. With a strong foundation in theoretical computer science, her research focuses on approximation algorithms. Passionate about integrating research into the teaching ecosystem, she is dedicated to creating an engaging academic environment. She especially enjoys teaching courses like algorithms, data structures, and discrete mathematics.
She has spent a decade of her academic and professional journey at the University of Delhi, beginning in July 2014. Over these ten years, she progressed from earning her bachelor’s and master’s degrees to completing a Ph.D. in Computer Science. In May 2023, she transitioned into a faculty role as an Assistant Professor at P.G.D.A.V. College. She began her current two-year visiting position at Northwestern in August 2024. This journey has deeply shaped her commitment to both research and teaching.
Ms. Rajni contributed to the following in last one year:
Title: Approximation Algorithms for Capacitated Facility Location with Outliers (Pdf)
Abstract:
Facility location and its many variants are well-studied NP-hard problems in the operations research and theoretical computer science communities. In the Classical Facility Location (FL) problem, we are given a set of clients and a set of potential facilities. Every facility has an opening cost, referred to as the facility cost. For every client and facility, the cost of serving the client by the facility is given by the distance between them, which is referred to as the service cost. The objective is to determine a subset of facilities to open and assign clients to the selected facilities in such a way that the total cost, which includes both the facility opening costs and the service costs, is minimized. We assume that the distances form a metric, i.e., the distances are symmetric and satisfy the triangle inequality. When the underlying distances do not form a metric, the facility location problem is at least as hard to approximate as the set cover. Hence, in this thesis, we will rely on the crucial assumption that the distances, and consequently the service costs, form a valid metric.
Facility location problems often arise in practical settings where additional constraints naturally arise. For example, in many real-world applications, a facility may have a limited capacity, restricting the number of clients it can serve. This gives rise to the Capacitated Facility Location (CFL) problem, where each facility has a maximum capacity, and the goal is to minimize the total cost of opening the facilities and serving clients while respecting these capacity constraints.
Consider scenarios where some clients are far away from majority of the clients, these clients might disproportionately affect the cost of the overall solution, leading to solutions that are not robust. To handle such cases, Charikar et al.[SODA'01] introduced a variant of facility location problem where a certain number of clients can be left unserved. These clients are popularly called as the outliers, and the respective facility location problem is called as the Facility Location with Outliers (FLO) problem. This is particularly useful when distant clients could significantly increase the overall cost or when the goal is to focus on serving a more representative subset of clients.
Though capacity and outlier constraints have been studied individually, it is quite natural to seek solutions that satisfy both constraints simultaneously, especially in complex real-world scenarios. For instance, in a logistics network, there may be a fixed number of distribution centers (facilities), each with limited capacity, but some remote customers may need to be excluded from the solution to keep costs manageable. Thus, a unified model that captures both capacity limitations and the ability to exclude outliers is highly relevant. This motivates us to study a generalization of CFL and FLO in this thesis, the Capacitated Facility Location with Outliers (CFLO) problem, which handles both capacity and outliers constraints simultaneously.
We first study the case when the facility opening costs are uniform, meaning all facilities have the same opening cost. We present a (6.373 + epsilon)-approximation algorithm using a 2-operation local search approach, where epsilon > 0 is a fixed constant. To the best of our knowledge, this is the first approximation algorithm for this problem. Furthermore, a simplified version of our local search algorithm and analysis leads to a (3.733 + epsilon)-approximation algorithm for the Capacitated Facility Location with Uniform Facility Cost problem, improving the current best-known factor of 4 by Kao[ISAAC'24] (which was achieved in a parallel work).
Next, we relax the assumption of uniform facility costs. We conjecture that the locality gap for Facility Location with Outliers in case non-uniform facility costs are unbounded, even in the uncapacitated setting and with constant factor violation in outliers. To support this conjecture, we provide an example where escaping the unbounded locality gap involves solving another instance of facility location with outliers problem itself. The unbounded locality gap example illustrates that obtaining a constant-factor approximation for CFLO, even with outlier and capacity violations, is difficult using the local search technique. Therefore, we turn our attention to LP-based algorithms. Both CFL (even with uniform capacities) and FLO are known to exhibit unbounded integrality gaps with respect to standard LP formulations. As a result, any algorithm that relies on the LP optimal solution as a lower bound will inevitably incur violations in both the capacity and outlier constraints. To make some progress on the problem, we focus on uniform capacities and introduce a tri-criteria approximation, where the solution approximates the cost within a constant factor while allowing small violations in both the capacity and outlier constraints. Specifically, we provide a O(1/epsilon^2) factor approximation for the problem, with violations in both capacities and outliers by a factor of (1 + epsilon), for a fixed constant epsilon > 0. This tri-criteria approximation could be useful in the future for eliminating violations in capacities, outliers, or both.
We then study the popular k-Median (kM) problem, which is similar to the Facility Location problem but instead of facility opening costs, it imposes a hard constraint on the number of facilities that can be opened. Both the k-Median and the k-Median with Outliers problems have been studied in the literature of approximation algorithms to obtain constant factor approximations. However, obtaining a constant-factor approximation for the Capacitated k-Median (CkM) problem remains one of the major open questions in the field. This challenge has led recent research to explore alternatives to traditional polynomial-time approximations. One promising direction is the study of fixed-parameter tractable (FPT) approximations. Not only have researchers managed to obtain constant-factor approximations (without violations) for the CkM problem, but they have also improved approximations for the k-Median and k-Median with Outliers problems by allowing the running time to be FPT in parameters like k and the number of outliers. Building on these advances in FPT approximations, we study FPT approximation for the Capacitated k-Median with Outliers (CkMO) problem. Specifically, we present an approximation-preserving reduction from CkMO to CkM, which runs in FPT time with respect to k, the number of outliers, and epsilon, where epsilon > 0 is a small constant. As a corollary, by using the best-known approximation for the CkM problem, we obtain a (3 + epsilon)-approximation algorithm for CkMO, which runs in FPT time with respect to k, the number of outliers, and epsilon.
The thesis thus contributes to the ongoing effort to understand and improve the approximation algorithms for capacitated facility location problems, particularly when outliers are allowed.
