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


Ph.D. Underprogress

  • 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 Projects

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.