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 capcitated variants of data placement problem, k-median, k-FLP and knapsack median.

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.

Network Algorithms (Limited Work)

Several types of attacks on ad hoc networks have been discussed in literature. Some of these (blackhole or grey holes attack, rushing attack, wormhole attacks) cripple the network by disrupting the route of the legitimate packets while others (flooding attack) inject too many extra packets in the system thereby consuming system resources like bandwidth, memory/computational power of nodes. We are interested in devising methods to protect the routing protocols in ad hoc networks against various types of attacks or reduce the impact of the attacks.

Data Mining and Bio-informatics (Earlier Work)

Bi-clustering and Bi-clustering Ensembles of Gene Expression Data.

Research Guidance

Ph.D. Completed


Ph.D. Underprogress

  • Aditya Pancholi (Jointly with Dr. Sambuddha Roy) (DoReg: May 2014)
  • Sapna Grover (DoReg: June 2014)

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

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.