My primary area of interest include 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 GuidancePh.D. Completed
- Sandhya Aneja
- Seema Aggarwal
- Manisha Bansal
- Parvaneh Mansouri (Jointly with Dr. Babak Asady)
- Geeta Gupta
- Sonika Thakral (Jointly with Dr. Yogish Sabharwal)
- Rahul Johari (Jointly with Dr. Sandhya Khurana)
- Sapna Grover (DoReg: May 5, 2017)
- Rajni (DoReg: November 11, 2019)
Research Projects (Major Grants/Research Collaboration)
- Principal Investigator, University Research Grant for project titled "Approximation Algorithms for capacitated facility location problems" October, 2015 onwards.
- 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 Projects2018 - 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
- Approximation Algorithms for Priority Facility Location Problem. Sachin Kashyap and Moksh Makhija (Jointly with Aditya Pancholi)
- 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)
- 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.