rkhandekar gmail com

Contact Address: IBM T.J. Watson research center 19 Skyline drive, Hawthorne, NY 10532-1596

I am a Research Staff Member in the department of Data Intensive Systems and Analytics at IBM T.J. Watson research center.
Here is my new homepage that is being created: Rohit Khandekar - IBM research.

Research Interests

My research interests include theoretical and practical aspects related to combinatorial optimization, approximation algorithms, algorithmic game theory, and mathematical programming. In particular, my work includes approximation algorithms for facility location problems, network design and routing, graph partitioning, and approximation schemes for linear and convex programming problems.

1. R. Khandekar, G. Kortsarz, and Z. Nutov.
   Approximating Fault-Tolerant Group-Steiner Problems
   In Proceedings, Foundations of Software Technology and Theoretical Computer Science (FSTTCS) , 2009.

2. R. Khandekar, K. Hildrum, S. Parekh, D. Rajan, J. Sethuraman, and J. Wolf.
   Bounded Size Graph Clustering with Applications to Stream Processing.
   In Proceedings, Foundations of Software Technology and Theoretical Computer Science (FSTTCS) , 2009.

3. R. Khandekar, K. Hildrum, S. Parekh, D. Rajan, J. Wolf, K.-L. Wu, H. Andrade, and B. Gedik.
   COLA: Optimizing Stream Processing Applications Via Graph Partitioning.
   In Proceedings, ACM/IFIP/USENIX 10th International Middleware Conference, 2009.

4. R. Khandekar, T. Kimbrel, K. Makarychev, and M. Sviridenko.
   On Hardness of Pricing Items for Single-Minded Bidders.
   In Proceedings, 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2009.

5. B. Awerbuch, Z. Fu, and R. Khandekar.
   Stateless Distributed Algorithms for Generalized Packing Linear Programs.
   In Proceedings, 28th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), 2009.

6. R. Garg and R. Khandekar.
   Gradient Descent with Sparsification: An iterative algorithm for sparse recovery with restricted isometry property. [PDF]
   In Proceedings, 26th International Conference on Machine Learning (ICML), 2009.

7. N. Bansal, Z. Friggstad, R. Khandekar, and M. Salavatipour.
   A Logarithmic Approximation for the Unsplittable Flow on Line Graphs. [PDF]
   In Proceedings, 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009.

8. L. Fleischer, R. Garg, S. Kapoor, R. Khandekar, and A. Saberi.
   A Fast and Simple algorithm for Computing Market Equilibria.
   In Proceedings, 4th Workshop on Internet and Network Economics (WINE), Lecture Notes in Computer Science, 2008.

9. R. Khandekar, G. Kortsarz, V. Mirrokni, M. Salavatipour.
   Two-stage Robust Network Design with Exponential Scenarios.
   In Proceedings, 16th European Symposium on Algorithms (ESA), Lecture Notes in Computer Science, 2008.

10. B. Awerbuch and R. Khandekar.
    Stateless Distributed Near Optimal Maximum Multi-Commodity Flow.
    In Proceedings, 27th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), 2008.

11. B. Awerbuch and R. Khandekar.
    Greedy Distributed Optimization of Unsplittable Multi-Commodity Flows.
    In Proceedings, 27th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), 2008.

12. B. Awerbuch and R. Khandekar.
    Cost Sharing Machanisms for Near-Optimal Traffic Aggregation and Network Design.
    In Proceedings, 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2008.

13. J. Cheriyan, H. Karloff, R. Khandekar, and J. Koenemann.
    On the Integrality Ratio for Tree Augmentation. [PDF]
    In Operations Research Letters, 2008.

14. B. Awerbuch and R. Khandekar.
    Stateless Distributed Gradient Descent for Positive Linear Programs. [PDF]
    In Proceedings, 40th Annual ACM Symposium on Theory of Computing (STOC), 2008.
    Full version appeared In SIAM Journal of Computing, 38(6), 2468--2486, 2009.

15. N. Bansal, R. Khandekar, and V. Nagarajan.
    Additive Gurantees for Degree Bounded Directed Network Design. [PDF]
    In Proceedings, 40th Annual ACM Symposium on Theory of Computing (STOC), 2008.

16. B. Awerbuch and R. Khandekar.
    Stateless Near Optimal Flow Control with Poly-logarithmic Convergence. [PDF]
    In Proceedings, 8th Latin American Theoretical Informatics (LATIN), 2008.

17. B. Awerbuch, Y. Azar, and R. Khandekar.
    Fast Load Balancing via Bounded Best Response. [PDF]
    In Proceedings, 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008.

18. N. Bansal, H.-L. Chan, R. Khandekar, K. Pruhs, B. Schieber, and C. Stein.
    Non-Preemptive Min-Sum Scheduling with Resource Augmentation. [PDF]
    In Proceedings, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2007.

19. B. Awerbuch and R. Khandekar.
    Greedy Distributed Optimization of Multi-Commodity Flows. [PDF]
    In Proceedings, 26th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), 2007.

20. B. Awerbuch and R. Khandekar.
    Distributed Network Monitoring and Multicommodity flows: A Primal-Dual Approach. [PDF]
    In Proceedings, 26th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), 2007.

21. B. Awerbuch and R. Khandekar.
    On Cost Sharing Mechanisms in the Network Design Game. [PDF]
    In Proceedings, 26th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), 2007.

22. B. Awerbuch and R. Khandekar.
    Minimizing the Total Cost of Network Measurements in a Distributed Manner: A Primal-Dual Approach. [PDF]
    In Proceedings, 26th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), 2007.

23. B. Awerbuch, R. Khandekar, and S. Rao.
    Distributed Algorithms for Multicommodity Flow Problems via Approximate Steepest Descent Framework. [PDF]
    In Proceedings, 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 949--957, 2007.

24. R. Khandekar and V. Pandit.
    Offline Sorting Buffers On Line.
    In Proceedings, 17th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science 4288, pages 81--89, 2006.

25. R. Khandekar, S. Rao, and U. Vazirani.
    Graph Partitioning using Single Commodity Flows. [PDF]
    In Proceedings, 38th Annual ACM Symposium on Theory of Computing (STOC), pages 385--390, 2006.
    Full version appeared In J. ACM, 56(4), 2009. 2008.

26. R. Khandekar and V. Pandit.
    Online Sorting Buffers On Line. [PS]
    In Proceedings, 23rd International Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, pages 584--595, 2006.

27. N. Devanur, N. Garg, R. Khandekar, V. Pandit, A. Saberi, and V. V. Vazirani.
    Price of Anarchy, Locality Gap, and a Network Service Provider Game. [PDF]
    In Proceedings, 1st Workshop on Internet and Network Economics (WINE), Lecture Notes in Computer Science 3828, pages 1046--1055, 2005.

28. N. Garg, R. Khandekar, and V. Pandit.
    Improved Approximation for Universal Facility Location. [PDF]
    In Proceedings, 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 959--960, 2005.

29. R. Khandekar.
    Lagrangian Relaxation based Algorithms for Convex Programming Problems [Abstract (PS)] [Thesis (PS.GZ)]
    Supervisor: Naveen Garg
    Indian Institute of Technology Delhi, March 2004.

30. P. Chaudhuri, R. Khandekar, D. Sethi, and P. Kalra.
    Collision-free Exploration of Virtual Environments. [PDF]
    In Proceedings, Computer Graphics International (CGI), pages 188--195, 2004.

31. N. Garg, R. Khandekar.
    Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries. [PDF]
    In Proceedings, 12th European Symposium on Algorithms (ESA), Lecture Notes in Computer Science 3221, pages 371--382, 2004.

32. N. Garg, R. Khandekar, K. Kunal, and V. Pandit.
    Bandwidth Maximization in Multicasting. [PS]
    In Proceedings, 11th European Symposium on Algorithms (ESA), Lecture Notes in Computer Science 2832, pages 242--253, 2003.

33. N. Garg and R. Khandekar.
    Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems. [PS]
    In Proceedings, 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 500--509, 2002.

34. V. Arya, N. Garg, R. Khandekar, K. Munagala, A. Meyerson, and V. Pandit.
    Local Search Heuristics for $k$-median and Facility Location Problems. [PS]
    In Proceedings, 33rd Annual ACM Symposium on Theory of Computing (STOC), pages 21--29, 2001.
    Full version appeared In SIAM Journal of Computing, 33(3), 544--562, 2004.

35. N. Garg, R. Khandekar, G. Konjevod. R. Ravi, F.S. Salman, and A. Sinha.
    On the Integrality Gap of a Natural Formulation of the Single-Sink Buy-at-bulk Network Design Problem. [PS]
    In Proceedings, 8th Conference on Integer Programming \& Combinatorial Optimization (IPCO), Lecture Notes in Computer Science 2081, pages 170--184, 2001.

36. N. Garg, R. Khandekar, and K. Talwar.
    Covering a Laminar Family.
    Manuscript, 2000.

37. R. Khandekar and K. Talwar
    Memory Management Technique solves Graph Coloring Problem.
    Manuscript, 1999.