Skip to content
Viswanath Nagarajan site logo
  • Publications
  • Papers By Topic
    • Papers By Topic
    • Network Design
    • Vehicle Routing
    • Scheduling
    • Online Algorithms
    • Stochastic Optimization
  • Teaching
    • Teaching
    • Approximation & Online Algorithms (Fall ’24)
    • Approximation & Online Algorithms (Winter ’21)
    • Approximation Algorithms
  • Students
  • Papers By Topic
    • Papers By Topic
    • Network Design
    • Vehicle Routing
    • Scheduling
    • Online Algorithms
    • Stochastic Optimization

Network Design

  • 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. 
  • 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.
  • On Some Variants of Euclidean k-Supplier,
    with E. Lee and L. Wang, Operations Research Letters, 50(2), 115-121, 2022. DOI.
  • 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.
  • 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.
  • Approximating Max-Cut under Graph-MSO Constraints, with M. Koutecky, J. Lee and X. Shen, Operations Research Letters, 46(6), 592-598, 2018.
  • Approximating graph-constrained max-cut, with J. Lee and X. Shen,
    Mathematical Programming (B), 172(1-2): 35-58, 2018.
    Preliminary version in IPCO 2016.
  • 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.
  • 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 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.
  • 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.
    Preliminary version in SODA 2011.
  • 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.
  • Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing, with R. Krishnaswamy, K. Pruhs and C. Stein, STOC, 2014.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Approximating the k-Multicut Problem, with D. Golovin and M. Singh, SODA 2006.

Viswanath Nagarajan

Michigan Engineering

1221 Beal Ave. Ann Arbor, MI 48109-2102

+1 (734) 647-7000

Contact the College

Engineering Intranet

© 2025 The Regents of the University of Michigan | Safety and Security | Acceptable Use |Privacy Policy |U-M Main

Login