Welcome to my Home Page. I completed my PhD in 2004. My supervisor was Prof. Naveen Garg. I am a Research Staff Member at IBM India Research Laboratory (IRL) since March 1999. I worked in IRL-Delhi till May 2009. Since then, I am working in IRL-Bengaluru.

I am interested in design of algorithms, local search heuristics for combinatorial optimization, and mathematical programming. My Ph.D. Thesis dealt with Local Search Heuristics for Facility Location Problems.

Selected Publications (For Full list, follow this link)

  • Decision Trees for Entity Identification: Approximation Algorithms and Hardness Results
    (with Venkatesan Chakaravarthy, Sambuddha Roy, Pranjal Awasthi, and Mukesh Mohania).
    ACM Transactions on Algorithms (TALG), Volume 7, No. 2, 2011; Preliminary version appeared in PODS 2007.

  • Online and offline algorithms for Sorting Buffers Problem on the Line Metric
    (with Rohit Khandekar).
    Journal of Discrete Algorithms (JDA), Volume 8, No. 1, pp:24--35, 2010. Preliminary versions appeared in STACS and ISAAC 2006.

  • Local Search Heuristics for k-median and Facility Location Problems
    (with Vijay Arya, Naveen Garg, Rohit Khandekar, Kamesh Munagala, and Adam Meyerson).
    Siam Journal of Computing, Volume 33, No. 3, pp: 544--562, 2004. Preliminary version appeared in STOC 2001.

  • Robust Fingerprint Verification Using Structural Similarity
    (with Nalini Ratha, Ruud Bolle, and Vaibhav Vaish).
    IEEE Workshop on Applications of Computer Vision (WACV) 2000.