# Neelima Gupta

## Department of Computer Science, University of Delhi

# Research Calendar

My primary area of interest include Approximation Algorithms.

## Approximation Algorithms

Network design problems occur naturally at many places. For example, a bank may want to install a number of ATMs in a city. Each location in the city is associated with an installation cost. The bank would be interested in identifying the locations to install these ATMs in such a way that the total installation cost plus the cost to service its clients is minimized. This is a typical example of a facility location problem where the ATMs serve as the facilities. Many similar examples can be quoted for the problem such as setting up of fire-brigade stations. In case of the problem of setting up of fire-brigade stations, one may also be interested in connecting these stations so that in case one station does not have a vagon to satisfy a client, the same can be obtained from a nearby station. In such a case, one would be interested in identifying the locations where in addition to the installation cost and service cost, the cost of connecting the fire-brigade stations is also taken into account. This is an example of a \lq connected \rq facility location problem. In another variation of fire-brigade problem, one may specify the maximum number of wagons available at a particular station. This gives rise to what is known as \lq capacitated \rq facility location problem. These problems are known to be NP-hard. The group is working on developing approximation algorithm for variants of facility location problems. In particular, we are looking at capacitated variants of data placement problem, k-median, k-FLP and knapsack median, facility location with penalty/outliers.

**For doing Ph.D. with me students with Mathematics background are preferred. Preferably an M.Sc. (Mathematics)/M.Sc.(Operational Research) from University of Delhi.**

## Research Guidance

**Ph.D. Completed**

- Sandhya Aneja
- Seema Aggarwal
- Manisha Bansal
- Parvaneh Mansouri (Jointly with Babak Asady)
- Geeta Gupta
- Sonika Thakral (Jointly with Yogish Sabharwal)
- Rahul Johari (Jointly with Sandhya Khurana)

**Ph.D. Underprogress**

- Sapna Grover (DoReg: May 5, 2017)
- Rajni (DoReg: November 11, 2019)
- Maulein Pathak (DoReg: February 2022) (Jointly with Yogish Sabharwal)
- Manisha Wadhwa (DoReg: February 2022) (Jointly with Sanjay Madria)

## Research Projects (Completed)

- Principal Investigator, FRP grant, "Efficient and Scalable Parallel Algorithms for Graph Spanners" October 2021 - June 2022.
- Principal Investigator, University Research Grant for project titled "Approximation Algorithms for capacitated facility location problems" October, 2015 - 2016
- Principal Investigator, University Research Grant for project titled "Approximation Algorithms for Replica Placement Problem" October, 2014 -2015. completed
- Principal Investigator, University Research Grant for project titled "Analysis of Gene Expression Data using Bi-Clustering Ensemble Technique" March 2010 - March 2013. Completed.
- Principal Investigator, University Research Grant for project titled "Analysis of Gene Expression Data" 2007-March 2010, completed.

## Master's Projects

**2020 - 2021**

- Testing of DUCS OfficeAutomation tool. Hitesh Yadav

**2019 - 2020**

- DUCS OfficeAutomation. Ruman Saleem, Swati Gautam and, Tanya Singhal

**2018 - 2019**

- Approximation Algorithms for Facility Location Problems with Penalties/Outliers and for ordered $k$-median problem. Abhilasha Gupta and Rajni
- Approximation Algorithms for Ordered k-median. Rajni
- Approximation Algorithms for Facility Location with Outliers. Abhilasha Gupta

**2016 - 2017**

- Approximation Algorithms for Priority Facility Location Problem. Sachin Kashyap and Moksh Makhija (Jointly with Aditya Pancholi)

**2015 - 2016**

- Design and Implementation of Classification Algorithms in OpenMP. Sonika Gupta and Juhi Jain (Jointly with Vipin Kumar)
- Design and Implementation of Classification Algorithms in Matlab. Aakriti, Darshika and Shikha (Jointly with Vipin Kumar)
- Design and Implementation of Classification Algorithms in MPI. Saurabh (Jointly with Sandhya Aneja)

**2014 - 2015**

- Approximation Algorithms for Replica Placement Problem: Anshul Aggarwal, Sachin Sharma (Jointly with Yogish Sabharwal)

**2013 - 2014**

- Approximation Algorithms for Replica Placement Problem : Kanika Gupta, Parul Garg, Ankur Sachdeva, Nirbhay (jointly with Yogish Sabharwal)
- Developing software for UG Admissions: Manisha, Avni, Tanu, Kirti, Mayank (Jointly with Aditya Pancholi)
- Developing software for Center Placement Cell: Navdeep and Shailendra (Jointly with Aditya Pancholi)
- Developing Biclustering Ensemble Tool: Navdeep and Shailendra.

**2012 - 2013**

- Approximation Algorithms for Replica Placement Problem: Stuti Chawla (jointly with Yogish Sabharwal)
- Approximation Algorithms for Interval Scheduling Problem: Mohit Narula (jointly with Sambuddha Roy)

**2011 - 2012**

- Approximation Algorithms for Data Placement problems : Sakshi, Archita
- Approximation algorithms for scheduling problems : Neha Bansal, Vijaya Goel, and Manish Dawar
- Approximation algorithms for Multi Organisation Scheduling problems : Neha Lawaria and Pankaj Kumar
- Routing in Delay Tolerant Networks : Garima and Sonia

**2010 - 2011**

- Efficient Routing in Delay Tolerant Networks : Divya Gaur and Surbhi Tripathi
- Ensemble techniques for bi-clustering problem : Deepika Bisht and Soniya Verma
- Approximation Algorithms for Facility Location Problem : Sapna Grover and Apurv Milind
- Approximation Algorithms for Data placement problem : Swati Singhal

**2009 - 2010**

- Approximation algorithms for clustering problems : Aditya Pancholi
- Parallel SAT : Ashish Mann and Vashita Arora
- Multi-core SAT : Amrita Goel and Hunarr Pahwa
- Routing in ad hoc networks : Megha Gupta and Simmi Singhal

**2008 - 2009**

- Subsequence Mining : Neha Jain and Leena Singhal
- Bi-clustering : Ishan Qureshi, Surbhi Bajaj

**2006 - 2007**

- Pattern Discovery Algorithms allowing Wildcard Characters : Ashish Juneja and Savneet Kaur
- Pattern Discovery Algorithms with Mismatches : Pooja Sinha and Shweta Mehra

**2005 - 2006**

- Implementation of Parallel Algorithms for Data Mining (jointly with Dr. Vasudha Bhatanagar) : Ashish Mangla and Ashwani Garg
- Implementation of Algorithms for identifying modules in Biological Networks.
- Implementation of Parallel Algorithms for Matrix Computations : Kapil and Tushir Aggarwal
- Implementation of Parallel Algorithms for Graph Problems.