Neelima Gupta

Biography

PhD (Computer Science) Indian Institute of Technology (IIT), Delhi. 1998 M.Tech (Computer Sc.) Indian Institute of Technology (IIT), Delhi. 1989 M. Sc. (Maths) Indian Institute of Technology (IIT), Delhi. 1987 B. Sc. (H) Maths Hindu College, University of Delhi. 1985 Certificate (French) Stephen’s College, University of Delhi. 2017

Research Interest

My primary areas of interest include ‘algorithms’ and ‘data mining’. 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 vagons 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. I am working on developing approximation algorithm for these problems. Various approaches like \lq local search \rq and \lq primal-dual \rq have been used for the purpose. In particular, we are looking at capcitated variants of data placement problem, k-median, k-FLP and knapsack median. Network Algorithms (Limited Work) In our daily life we encounter several networks that are partitioned. That is there is no persistent connectivity between the two partitions. Thus a message from one partition to another partition must wait for the connection to be established and hence must be tolerant towards the inherent delays in the delivery. Such networks are thus called Delay Tolerant Networks(DTNs). Connections in DTNs are established by way of some mobile entities which may move from one partition to another. We are interested in devising good routing algorithms for DTNs. Earlier 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.