The copyright for most of these papers are with the respective publishers. The papers posted here are for personal use only.

Below is a reverse chronological list of papers (based on the latest versions).

For a list of papers classified by topic, see this link.

**2018**

- Approximating Max-Cut under Graph-MSO Constraints, with M. Koutecky, J. Lee and X. Shen,

manuscript on arXiv. - Stochastic Load Balancing on Unrelated Machines, with A. Gupta, A. Kumar and X.Shen,

*SODA*, 2018.

**2017**

- Approximation algorithms for stochastic k-TSP, with A. Ene and R. Saket,

*FSTTCS*, 2017. - Online Covering with Sum of Lq-norm Objectives, with X.Shen,

*ICALP*, 2017. - Adaptive Submodular Ranking, with F. Navidi and P. Kambadur,

*IPCO*, 2017. - Minimum Makespan VRP with Compatibility Constraints, with M. Yu and S. Shen,

*CPAIOR*, 2017. - Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions, with A. Gupta and S. Singla,

*SODA*, 2017 - Approximation Algorithms for Optimal Decision Trees and Adaptive TSP, with A. Gupta and R. Ravi,

*Mathematics of Operations Research*, 42(3): 876-896, 2017.

Preliminary version in*ICALP*2010. - Approximation-Friendly Discrepancy Rounding, with N. Bansal,

“A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek”,

editors Martin Loebl, Jaroslav Nešetřil, Robin Thomas, 89-114, 2017

Preliminary version in*IPCO*, 2016.

**2016**

- Online Algorithms for Covering and Packing Problems with Convex Objectives, with Y. Azar, N. Buchbinder, H. Chan, S. Chen, IR. Cohen, A. Gupta, Z. Huang, N. Kang, J. Naor, D. Panigrahi.

*FOCS*2016.

This is a merged version of three independent papers: 1, 2, 3. - Max-Cut under Graph Constraints, with J. Lee and X. Shen,

*IPCO*, 2016. - Algorithms and Adaptivity Gaps for Stochastic Probing, with A. Gupta and S. Singla,

*SODA*, 2016. - Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets, with A. Gupta, and R. Ravi,

*ACM Transactions on Algorithms*, 12(1), 2016. - Approximation Algorithms for Inventory Problems with Submodular or Routing Costs, with C. Shi,

*Mathematical Programming (A)*, 160(1-2): 225-244, 2016. - Algorithms for Hub Label Optimization, with M. Babenko, A. Goldberg and A. Gupta,

*ACM Transactions on Algorithms*, 13(1), 2016.

Preliminary version in*ICALP*2013. - Minimum Latency Submodular-Cover, with S. Im and R. van der Zwaan,

*ACM Transactions on Algorithms*, 13(1), 2016.

Preliminary version in*ICALP*2012. - Locating Depots for Capacitated Vehicle Routing, with I. L. Goertz,

*Networks*68(2): 94-103, 2016.

Preliminary version in*APPROX*2011. - Capacitated Vehicle Routing with Non-Uniform Speeds, with I. L. Goertz, M. Molinaro and R. Ravi,

*Mathematics of Operations Research*, 41(1): 318-331, 2016.

Preliminary version in*IPCO*2011.

**2015**

- The Container Selection Problem, with K. Sarpatwar, B. Schieber, H. Shachnai and J. Wolf,

*APPROX*, 2015. - Minimum Congestion Mapping in a Cloud, with N. Bansal, K.W. Lee and M. Zafer,

*SIAM Journal on Computing*, 44(3), 819-843, 2015.

Preliminary version in PODC 2011. - 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. - Approximation Algorithms for Stochastic Orienteering, with A. Gupta, R. Krishnaswamy, and R. Ravi,

*Mathematics of Operations Research*, 40(1), 2015.

Preliminary version in*SODA*2012. - Stochastic Knapsack (short survey), Encyclopedia of Algorithms, 2015.
- Minimum Makespan Multi-Vehicle Dial-a-Ride, with I. L. Goertz and R. Ravi,

*ACM Transactions on Algorithms,*11(3):23, 2015.

Preliminary version in*ESA*2009. - On the Adaptivity Gap of Stochastic Orienteering, with N. Bansal,

*Mathematical Programming (B)*, 154(1-2), 145-172, 2015.

Preliminary version in*IPCO*2014.

**2014**

- The X-flex cross-platform scheduler: who’s the fairest of them all?, with J. Wolf, Z. Nabi, R. Saccone, R. Wagle, K. Hildrum, E. Pring and K. Sarpatwar, Middleware Conference (Industry track), 2014.
- Approximating Sparse Covering Integer Programs Online, with A. Gupta,

*Mathematics of Operations Research*, 39(4): 998-1011, 2014.

Preliminary version in*ICALP*2012. - Better Scalable Algorithms for Broadcast Scheduling, with N. Bansal and R. Krishnaswamy,

*ACM Transactions on Algorithms*11(1):3, 2014.

Preliminary version in*ICALP*2010. - Thresholded Covering Algorithms for Robust and Max-Min Optimization, with A. Gupta and R. Ravi,

*Mathematical Programming (A)*, 146(1-2), 583-615, 2014.

Preliminary version in*ICALP*2010. - Min-Max Graph Partitioning and Small Set Expansion,

with N. Bansal, U. Feige, R. Krauthgamer, K. Makarychev, J. Naor and R. Schwartz,

*SIAM Journal on Computing*, 43(2), 872-904, 2014.

Preliminary version in*FOCS*2011. - 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.

**2013**

- FlowFlex: Malleable Scheduling for Flows of MapReduce Jobs, with J. Wolf, A. Balmin, and K. Hildrum,

Middleware Conference, 2013. - The Approximability of the Binary Paintshop Problem, with A. Gupta, S. Kale, R. Saket and B. Schieber,

*APPROX*, 2013. - On Generalizations of Network Design Problems with Degree Bounds,

with N. Bansal, R. Khandekar, J. Konemann and B. Peis,

*Mathematical Programming (A)*, 141(1), 479-506, 2013.

Preliminary version in*IPCO*2010. - A Stochastic Probing Problem with Applications, with A. Gupta,

*IPCO*, 2013. - The Euclidean k-Supplier Problem, with B. Schieber and H. Shachnai,

*IPCO*2013. - Thrifty Algorithms for Multi-stage Robust Optimization, with A. Gupta and V. V. Vazirani,

*IPCO*2013.

**2012**

- 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. - Solving Packing Integer Programs via Randomized Rounding with Alterations,

with N. Bansal, N. Korula and A. Srinivasan,

*Theory of Computing*, 8(1), 533-565, 2012.

Preliminary version in*IPCO*2010. - When LP is the cure for your matching woes: Improved bounds for stochastic matchings, with N. Bansal, A. Gupta, J. Li, J. Mestre and A. Rudra,

*Algorithmica*, 63(4), 733-762, 2012.

Preliminary version in*ESA*2010. - Approximation Algorithms for Distance Constrained Vehicle Routing, with R. Ravi,

*Networks*, 59(2), 209-214, 2012.

Preliminary version in*APPROX*2006. - Stochastic Vehicle Routing with Recourse, with I.L. Goertz and R. Saket,

*ICALP*2012. - Approximation Algorithms for VRP with Stochastic Demands, with A. Gupta and R. Ravi,

*Operations Research*, 60(1), 123-127, 2012.

**2011**

- The Directed Orienteering Problem, with R. Ravi,

*Algorithmica*, 60(4), 1017-1030, 2011.

Preliminary version in*APPROX*2007.

**2010**

- Dial-a-Ride from k-forest, with A. Gupta, M.T. Hajiaghayi, and R. Ravi,

*ACM Transactions on Algorithms*, 6(2), 2010.

Preliminary version in*ESA*2007. - 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. - 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. - 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. - Non-Monotone Submodular Maximization with Matroid or Knapsack Constraints,

with J. Lee, V. Mirrokni and M. Sviridenko,

*SIAM Journal on Discrete Mathematics*, 23(4), 2053-2078, 2010.

Preliminary version in*STOC*2009.

**2009**

- Tight Bounds for Permutation Flowshop Scheduling, with M. Sviridenko,

*Mathematics of Operations Research*, 34(2), 417-427, 2009.

Preliminary version in*IPCO*2008. - Additive Guarantees for Degree Bounded Directed Network Design, with N. Bansal and R. Khandekar,

*SIAM Journal on Computing*, 39(4), 1413-1431, 2009.

Preliminary version in*STOC*2008. - On the Maximum Quadratic Assignment Problem, with M. Sviridenko,

*Mathematics of Operations Research*, 34(4), 859-868, 2009.

Preliminary version in*SODA*2009.

**2008**

- The Directed Minimum Latency Problem, with R. Ravi,

*APPROX*2008. - Exact Train Pathing, with A. G. Ranade,

*Journal of Scheduling*, 11(4), 279-297, 2008.

**2006**

- Approximating the k-Multicut Problem, with D. Golovin and M. Singh,

*SODA*2006.

**2005**

- Fairness and Optimality in Congestion Games, with D. Chakrabarty, A. Mehta, and V.V. Vazirani,

ACM Conference on Electronic Commerce (*EC*), 2005.