Vinayaka Pandit's Publications


Copyright Notice: Since most of these papers are published, the copyright has been transferred to the respective publishers. Therefore, the papers cannot be duplicated for commercial purposes. The following is ACM's copyright notice; other publishers have similar ones.

Copyright 199x by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted.


Papers on Approximation Algorithms and Combinatorial Optimization.


Papers on Databases and Data Mining.


Other Miscellaneous Papers.

Algorithms and Combinatorial Optimization

  • Scheduling Resources for throughput maximization.
    (with Venkatesan Chakaravarthy, Amit Kumar, Yogish Sabharwal, and Sambuddha Roy).
    To appear in the Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2011.

  • Finding Independent Sets in Unions of Perfect Graphs.
    (with Venkatesan Chakaravarthy, Yogish Sabharwal, and Sambuddha Roy).
    in the Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2010.

  • Varying Bandwidth Resource Allocation Problem with Bag Constraints.
    (with Venkatesan Chakaravarthy, Yogish Sabharwal, and Deva P. Seetharam).
    in the Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS) 2010.

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

  • Approximating Decision Trees with Multiway Branches
    (with Venkat Chakaravarthy, Yogish Sabharwal, and Sambuddha Roy).
    To appear in the proceedings of the International Conference on Automata, Langauages, and Programming (ICALP), 2009.

  • Analysis of Sampling Techniques for Association Rule Mining
    (with Venkat Chakaravarthy and Yogish Sabharwal).
    In the proceedings of the International Conference on Database Theory (ICDT), 2009.

  • Online and offline algorithms for Sorting Buffers Problem on the Line Metric
    (with Rohit Khandekar).
    Journal of Discrete Algorithms (JDA), vol 8, number 1, pp:24--35, 2010.

  • Order Scheduling Models: Hardness and Algorithms
    (with Naveen Garg and Amit Kumar).
    In the proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2007.

  • Decision Trees for Entity Identification: Approximation Algorithms and Hardness Results
    (with Venkatesan Chakaravarthy, Sambuddha Roy, Pranjal Awasthi, and Mukesh Mohania).
    In the proceedings of the 26th ACM Symposium on Principles of Database Systems (PODS) 2007.

  • Offline Sorting Buffers On Line
    (with Rohit Khandekar).
    In the proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC), 2006.

  • Online Sorting Buffers On Line
    (with Rohit Khandekar).
    In the Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science (STACS) 2006.

  • Improved Approximation for Universal Facility Location
    (with Naveen Garg and Rohit Khandekar).
    In the Proceedings of ACM-SIAM Symposium On Discrete Algorithms (SODA ) 2005.

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

  • Price of Anarchy, Locality Gap, and a Network Service Provider Game
    (with Nikhil Devanur, Naveen Garg, Rohit Khandekar, Amin Saberi, and Vijay Vazirani).
    In Proceedings of the First Workshop on Internet and Network Economics, WINE 2005.

  • Bandwidth Maximization in Multicasting
    (with Naveen Garg, Rohit Khandekar, and Keshav Kunal).
    Journal version under Submission. Preliminary version appeared in ESA 03.

  • Local Search for Budget Constrained $k$-median Problem
    (with Rohit Khandekar).
    IBM Research Report RI02012.

  • Approximation algorithms for Budget Constrained Auctions
    (with Rahul Garg and Vijay Kumar).
    in APPROX '01

  • Databases and Data Mining

  • Design and Analysis of Interaction Networks
    (with Kameshwaran Sampath and Sameep Mehta).
    To appear in the Proceedings of the twenty fifth AAAI Conference on Artificial Intelligence (AAAI), 2011

  • On Discovering Bucket Orders from Data
    (with Sreyash Kenkre and Arindam Khan).
    To appear in the Proceedings of the SIAM Conference on Data Mining (SDM), 2011

  • Outcome Aware Ranking in Interaction Networks
    (with S. Kameshwaran, Sameep Mehta, N. Viswanadham and Kashyap Dixit).
    In the Proceedings of the ACM Conference Information and Knowledge Management (CIKM), 2010

  • Analyses for Service Interaction Networks with Applications to Service Delivery
    (with S. Kameshwaran, Sameep Mehta, Gyana Parija, Sudhanshu Singh, and N. Viswanadham).
    In the Proceedings of the SIAM Conference on Data Mining (SDM), 2009

  • Analysis of Sampling Techniques for Association Rule Mining
    (with Venkat Chakaravarthy and Yogish Sabharwal).
    In the proceedings of the International Conference on Database Theory (ICDT), 2009.

  • Approximating Decision Trees with Multiway Branches
    (with Venkat Chakaravarthy, Yogish Sabharwal, and Sambuddha Roy).
    To appear in the proceedings of the International Conference on Automata, Langauages, and Programming (ICALP), 2009.

  • Decision Trees for Entity Identification: Approximation Algorithms and Hardness Results
    (with Venkatesan Chakaravarthy, Sambuddha Roy, Pranjal Awasthi, and Mukesh Mohania).
    In the proceedings of the 26th ACM Symposium on Principles of Database Systems (PODS) 2007.

  • Other Papers

  • Studying the evolution of skill profiles in distributed, specialization driven service delivery systems through work orchestration
    (with Shivali Agarwal, Sreyash Kenkre, and Bikram Sengupta).
    in the Proceedings of the Global Conference of the Service Research and Innovation Institute (SRII), 2011.

  • Extracting Dense Communities from Telecom Call Graphs
    (with Sougata Mukherjea, Amit Nanavati, Natwar Modani, Sambuddha Roy, and Amit Agarwal).
    Invited Paper in the Proceedings of the 3rd International Conference on Communication System Software and Middleware (COMSWARE), 2008

  • Efficient in-network evaluation of Multiple Queries
    (with Hui-bo Ji).
    In the proceedings of 13th International Conference on High Performance Computing, HiPC '06

  • Optimal Bitwise Register Allocation using Integer Linear Programming
    (with Rajkishore Barik, Christian Grothoff, Rahul Gupta, and Raghavendra Udupa).
    In the proceedings of the 19th workshop on Langauages and Compilers for Parallel Computing (LCPC), 2006

  • An Overview of the BlueGene/L Supercomputer
    (with Team BlueGene).
    IEEE Supercomputing Conference, SC02
  • Self-stabilizing maxima finding on general graphs
    (with Dhananjay Dhamdhere).
    IBM Research Report RI02009

  • An efficient decoding algorithm for WFA
    (with Raghavendra Udupa and Tanveer Faruquie).
    ICVGVIP 2000

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

  • A new decoding algorithm for weighted finite automata
    (with Raghavendra Udupa and Ashok Rao).
    Fifth IEEE Symposium on Intelligent Systems, Bangalore, 1996

  • Refereed Workshops (without Proceedings)

  • On scheduling aspects of critical jobs
    (with Venkat Chakaravarthy, Gyana Parija, and Sambuddha Roy).
    Biennial workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2007.

  • Self-Discovery on a hierarchical 3-dimensional torus
    (with Rahul Garg, Meeta Sharma, Jose Moreira, and Jose Castanos).
    SHAMAN'02 held with ACM Supercomputing Conference

  • Strategic Headcoun Planning of Multi-skilled BPO Back-office Process Agents with Recourse Transitions
    (with Gyana Parija, Tarun Kumar, and Sameep Mehta).
    11th Stoachastic Programming Conference (SPXI), 2007


  • Back to Vinayaka Pandit's Home Page