Network Design

Connectivity problems

• Approximation-Friendly Discrepancy Rounding, with N. Bansal, IPCO 2016.
• Thresholded Covering Algorithms for Robust and Max-Min Optimization, with A. Gupta and R. Ravi, Mathematical Programming, 146(1-2), 583-615, 2014. (Preliminary version in ICALP 2010.)
• Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing, with R. Krishnaswamy, K. Pruhs and C. Stein, ACM Symposium on Theory of Computing (STOC) 2014.
• Hallucination Helps: Energy Efficient Virtual Circuit Routing, with A. Antoniadis, S. Im, R. Krishnaswamy, B. Moseley, K. Pruhs and C. Stein, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.
• On Generalizations of Network Design Problems with Degree Bounds, with N. Bansal, R. Khandekar, J. Konemann and B. Peis, Mathematical Programming, 141(1), 479-506, 2013. (Preliminary version in IPCO 2010.)
• Algorithms for Hub Label Optimization, with M. Babenko, A. Goldberg and A. Gupta, International Colloquium on Automata, Languages and Programming (ICALP), 2013.
• Thrifty Algorithms for Multi-stage Robust Optimization, with A. Gupta and V. V. Vazirani, IPCO 2013.
• Multicast Routing for Energy Minimization Using Speed Scaling, with N. Bansal, A. Gupta, R. Krishnaswamy, K. Pruhs and C. Stein, Mediterranean Conference on Algorithms, 2012.
• Minimum Congestion Mapping in a Cloud, with N. Bansal, K.W. Lee and M. Zafer, ACM Symposium on Principles of Distributed Computing, 2011.
• Simpler Analysis of LP Extreme Points for Traveling Salesman and Survivable Network Design, with R. Ravi and M. Singh, Operations Research Letters, 38(3), 156-160, 2010.
• Additive Guarantees for Degree Bounded Directed Network Design, with N. Bansal and R. Khandekar, SIAM J. Computing, 39(4), 1413-1431, 2009. (Preliminary version in STOC 2008.)

Cut problems

• Min-Max Graph Partitioning and Small Set Expansion, with N. Bansal, U. Feige, R. Krauthgamer, K. Makarychev, J. Naor and R. Schwartz, SIAM J. Computing, 43(2), 872-904, 2014. (Preliminary version in FOCS 2011.)
• An Improved Approximation Algorithm for Requirement Cut, with A. Gupta and R. Ravi, Operations Research Letters, 38(4), 322-325, 2010.
• Approximation Algorithms for Requirement Cut on Graphs, with R. Ravi, Algorithmica, 56(2), 198-213, 2010. (Preliminary version in APPROX 2005.)
• Approximating the k-Multicut Problem, with D. Golovin and M. Singh, SODA 2006.

Clustering problems

• Max-Cut under Graph Constraints, with J. Lee and X. Shen, IPCO 2016.
• The Container Selection Problem, with K. Sarpatwar, B. Schieber, H. Shachnai and J. Wolf, Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), 2015.
• Facility Location with Matroid or Knapsack Constraints, with R. Krishnaswamy, A. Kumar, Y. Sabharwal and B. Saha, Mathematics of Operations Research, 40(2), 2015. (Preliminary version in SODA 2011.)
• The Euclidean k-Supplier Problem, with B. Schieber and H. Shachnai, IPCO 2013.
• A plant location guide for the unsure, with B. Anthony, V. Goyal, and A. Gupta, Mathematics of Operations Research, 35(1), 79-101, 2010. (Preliminary version in SODA 2008.)