Publications

The copyright for most of these papers is with the respective publisher. 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.

2024

• A General Framework for Sequential Batch-Testing, with R. Tan and A. Xu, 2024.
• Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover, with B. Harris, 2024.
• Semi-Bandit Learning for Monotone Stochastic Optimization, with A. Agarwal and R. Ghuge, FOCS, 2024.
• Informative Path Planning with Limited Adaptivity, with R. Tan and R. Ghuge, AISTATS, 2024.  
• The Power of Adaptivity for Stochastic Submodular Cover, with R. Ghuge and A. Gupta,
  Operations Research, 72(3): 1156-1176, 2024. DOI.
  Preliminary version in ICML, 2021. DOI.
• Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing,
  with R. Krishnaswamy, K. Pruhs and C. Stein,
  SIAM Journal on Computing, 53(3): 588-623, 2024. DOI.
  Preliminary version in STOC 2014. DOI.
• Online Generalized Network Design Under (Dis)Economies of Scale, with L. Wang,
  Mathematics of Operations Research, 49(1): 107-124, 2024. DOI.
  Preliminary version in SODA, 2021. DOI. 

2023

• Efficient Algorithms for Stochastic Ride-Pooling Assignment with Mixed Fleets, with Q. Luo, A. Sundt, Y. Yin, J. Vincent, M. Shahabi,
  Transportation Science, 57(4):908-936, 2023. DOI. 
• Minimum Cost Adaptive Submodular Cover, with H. Al-Thani and Y. Cui, preliminary version in SOSA 2023. DOI. 

2022

• An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem,
  with A. Agarwal and R. Ghuge, NeurIPS, 2022.
• Batched Dueling Bandits, with A. Agarwal and R. Ghuge,
  ICML, 2022. DOI.
• Non-Adaptive Stochastic Score Classification and Explainable Halfspace Evaluation,
  with R. Ghuge and A. Gupta, IPCO, 2022. DOI.
• Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems, with R. Ghuge,
  Mathematics of Operations Research, 47(2):1612-1630, 2022. DOI.
  Preliminary version in SODA, 2020. DOI.
• Improving Column-Generation for Vehicle Routing Problems via Random Coloring and Parallelization,
  with M. Yu and S. Shen, INFORMS Journal on Computing, 34(2): 953-973, 2022. DOI.
• Constrained Assortment Optimization under the Paired Combinatorial Logit Model,
  with R. Ghuge, J. Kwon and A. Sharma, Operations Research, 70(2): 786-804, 2022. DOI.
• Stochastic Makespan Minimization in Structured Set Systems, with A. Gupta, A. Kumar and X. Shen,
  Mathematical Programming, 192(1): 597-630, 2022. DOI.
  Preliminary version in IPCO, 2020.
• On Some Variants of Euclidean k-Supplier,
  with E. Lee and L. Wang, Operations Research Letters, 50(2), 115-121, 2022. DOI.

2021

• Stochastic Load Balancing on Unrelated Machines, with A. Gupta, A. Kumar and X.Shen,
  Mathematics of Operations Research, 46(1):115-133, 2021. DOI.
  Preliminary version in SODA, 2018. DOI. 

2020

• Online Covering with Sum of Lq-norm Objectives, with X.Shen, 
  Mathematical Programming (A), 184, 155–182, 2020. DOI.
  Preliminary version in ICALP, 2017. DOI.
• Adaptive Submodular Ranking and Routing, with F. Navidi and P. Kambadur,
  Operations Research, 68(3):856-877, 2020. DOI.
  Preliminary version in IPCO, 2017. DOI.
• The Euclidean k-Supplier Problem, with B. Schieber and H. Shachnai,
  Mathematics of Operations Research, 45(1):1-14, 2020. DOI.
  Preliminary version in IPCO 2013. DOI.
• Hallucination Helps: Energy Efficient Virtual Circuit Routing,
  with A. Antoniadis, S. Im, R. Krishnaswamy, B. Moseley, K. Pruhs and C. Stein,
  SIAM Journal on Computing, 49(1): 37-66, 2020. DOI.
  Preliminary version in SODA, 2014. DOI.
• Approximation Algorithms for the A Priori Traveling Repairman, with I.L. Goertz and F. Navidi,
  Operations Research Letters, 48(5), 599-606, 2020. DOI.

2019

• Optimal Decision Tree with Noisy Outcomes,
  with S. Jia, F. Navidi and R. Ravi, NeurIPS 2019. DOI. 
• Malleable scheduling for flows of jobs and applications to MapReduce,
  with J. Wolf, A. Balmin, and K. Hildrum, Journal of Scheduling, 22(4): 393-411, 2019. DOI.
  Preliminary version in Middleware 2013. 

2018

• Approximating Max-Cut under Graph-MSO Constraints, with M. Koutecky, J. Lee and X. Shen, 
  Operations Research Letters, 46(6), 592-598, 2018. DOI. 
• Approximating graph-constrained max-cut, with J. Lee and X. Shen,
  Mathematical Programming (B), 172(1-2): 35-58, 2018. DOI. 
  Preliminary version in IPCO 2016.
• An Approximation Algorithm for Vehicle Routing with Compatibility Constraints,
  with M. Yu and S. Shen, Operations Research Letters, 46(6), 579-584, 2018. DOI. 
  Preliminary version in CPAIOR 2017.

2017

• Approximation algorithms for stochastic k-TSP, with A. Ene and R. Saket,
  FSTTCS, 2017. DOI.
• Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions,
  with A. Gupta and S. Singla, SODA, 2017. DOI.
• Approximation Algorithms for Optimal Decision Trees and Adaptive TSP,
  with A. Gupta and R. Ravi, Mathematics of Operations Research, 42(3): 876-896, 2017. DOI.
  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. DOI. 
  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. DOI. 
  This is a merged version of three independent papers: 1, 2, 3.
• Algorithms and Adaptivity Gaps for Stochastic Probing, with A. Gupta and S. Singla,
  SODA, 2016. DOI.
• Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets,
  with A. Gupta, and R. Ravi, ACM Transactions on Algorithms, 12(1), 2016. DOI.
• Approximation Algorithms for Inventory Problems with Submodular or Routing Costs,
  with C. Shi, Mathematical Programming (A), 160(1-2): 225-244, 2016. DOI.
• Algorithms for Hub Label Optimization, with M. Babenko, A. Goldberg and A. Gupta,
  ACM Transactions on Algorithms, 13(1), 2016. DOI.
  Preliminary version in ICALP 2013.
• Minimum Latency Submodular-Cover, with S. Im and R. van der Zwaan,
  ACM Transactions on Algorithms, 13(1), 2016. DOI.
  Preliminary version in ICALP 2012.
• Locating Depots for Capacitated Vehicle Routing, with I. L. Goertz, 
  Networks 68(2): 94-103, 2016. DOI.
  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. DOI.
  Preliminary version in IPCO 2011.
• Stochastic Knapsack (short survey), Encyclopedia of Algorithms, 2016. DOI.

2015

• The Container Selection Problem, with K. Sarpatwar, B. Schieber, H. Shachnai and J. Wolf, 
  APPROX, 2015. DOI.
• Minimum Congestion Mapping in a Cloud, with N. Bansal, K.W. Lee and M. Zafer,
  SIAM Journal on Computing, 44(3), 819-843, 2015. DOI.
  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. DOI.
  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. DOI.
  Preliminary version in SODA 2012.
• Minimum Makespan Multi-Vehicle Dial-a-Ride, with I. L. Goertz and R. Ravi,
  ACM Transactions on Algorithms, 11(3):23, 2015. DOI.
  Preliminary version in ESA 2009.
• On the Adaptivity Gap of Stochastic Orienteering, with N. Bansal,
  Mathematical Programming (B), 154(1-2), 145-172, 2015. DOI.
  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. DOI.
• Approximating Sparse Covering Integer Programs Online, with A. Gupta,
  Mathematics of Operations Research, 39(4): 998-1011, 2014. DOI.
  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. DOI.
  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. DOI.
  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. DOI.
  Preliminary version in FOCS 2011.

2013

• The Approximability of the Binary Paintshop Problem,
  with A. Gupta, S. Kale, R. Saket and B. Schieber, APPROX, 2013. DOI.
• 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. DOI.
  Preliminary version in IPCO 2010.
• A Stochastic Probing Problem with Applications, with A. Gupta, 
  IPCO, 2013. DOI.
• Thrifty Algorithms for Multi-stage Robust Optimization,
  with A. Gupta and V. V. Vazirani, IPCO 2013. DOI.

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. DOI.
• 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. DOI.
  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. DOI.
  Preliminary version in ESA 2010.
• Approximation Algorithms for Distance Constrained Vehicle Routing, with R. Ravi,
  Networks, 59(2), 209-214, 2012. DOI.
  Preliminary version in APPROX 2006.
• Stochastic Vehicle Routing with Recourse, with I.L. Goertz and R. Saket, 
  ICALP 2012. DOI.
• Approximation Algorithms for VRP with Stochastic Demands, with A. Gupta and R. Ravi,
  Operations Research, 60(1), 123-127, 2012. DOI.

2011

• The Directed Orienteering Problem, with R. Ravi,
  Algorithmica, 60(4), 1017-1030, 2011. DOI.
  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. DOI.
  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. DOI.
• A plant location guide for the unsure, with B. Anthony, V. Goyal, and A. Gupta,
  Mathematics of Operations Research, 35(1), 79-101, 2010. DOI.
  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. DOI.
• Approximation Algorithms for Requirement Cut on Graphs, with R. Ravi,
  Algorithmica, 56(2), 198-213, 2010. DOI.
  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. DOI.
  Preliminary version in STOC 2009.

2009

• Tight Bounds for Permutation Flowshop Scheduling, with M. Sviridenko,
  Mathematics of Operations Research, 34(2), 417-427, 2009. DOI.
  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. DOI.
  Preliminary version in STOC 2008.
• On the Maximum Quadratic Assignment Problem, with M. Sviridenko,
  Mathematics of Operations Research, 34(4), 859-868, 2009. DOI.
  Preliminary version in SODA 2009.

2008

• The Directed Minimum Latency Problem, with R. Ravi,
  APPROX 2008. DOI.
• Exact Train Pathing, with A. G. Ranade,
  Journal of Scheduling, 11(4), 279-297, 2008. DOI.

2006

• Approximating the k-Multicut Problem, with D. Golovin and M. Singh,
  SODA 2006. DOI.

2005

• Fairness and Optimality in Congestion Games, with D. Chakrabarty, A. Mehta, and V.V. Vazirani,
  ACM Conference on Electronic Commerce (EC), 2005. DOI.