Skip to content
Connectivity problems
Approximation-Friendly Discrepancy Rounding , with N. Bansal, IPCO 2016.Algorithms for Hub Label Optimization , with M. Babenko, A. Goldberg and A. Gupta, ACM Transactions on Algorithms , 13(1), 2016. ICALP 2013.Minimum Congestion Mapping in a Cloud , with N. Bansal, K.W. Lee and M. Zafer, SIAM Journal on Computing , 44(3), 819-843, 2015. Thresholded Covering Algorithms for Robust and Max-Min Optimization , with A. Gupta and R. Ravi, Mathematical Programming , 146(1-2), 583-615, 2014. ICALP 2010.Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing , with R. Krishnaswamy, K. Pruhs and C. Stein, STOC, 2014.Hallucination Helps: Energy Efficient Virtual Circuit Routing , with A. Antoniadis, S. Im, R. Krishnaswamy, B. Moseley, K. Pruhs and C. Stein, 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. IPCO 2010.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.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. 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. 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, 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. 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. SODA 2008.
