Viswanath Nagarajan

Oper. Res. Lett., 2026

2025

Introduction: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2023 Special Issue.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, October, 2025

Identifying Approximate Minimizers under Stochastic Uncertainty.

[BibT_eX]

[DOI]

Hessa Al-Thani

CoRR, April, 2025

Approximation Algorithms for Stochastic Optimization (Dagstuhl Seminar 25132).

[BibT_eX]

[DOI]

Lisa Hellerstein

Kevin Schewior

Dagstuhl Reports, March, 2025

A general framework for sequential batch-testing.

[BibT_eX]

[DOI]

Rayen Tan

Alex Xu

Oper. Res. Lett., 2025

Nonadaptive Stochastic Score Classification and Explainable Half-Space Evaluation.

[BibT_eX]

[DOI]

Oper. Res., 2025

Sequential Testing with Subadditive Costs.

[BibT_eX]

[DOI]

Blake Harris

Rayen Tan

Proceedings of the Integer Programming and Combinatorial Optimization, 2025

Identifying Approximate Minimizers Under Stochastic Uncertainity.

[BibT_eX]

[DOI]

Hessa Al-Thani

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

2024

Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing.

[BibT_eX]

[DOI]

Kirk Pruhs

Clifford Stein

SIAM J. Comput., 2024

Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover.

[BibT_eX]

[DOI]

Blake Harris

CoRR, 2024

Semi-Bandit Learning for Monotone Stochastic Optimization.

[BibT_eX]

[DOI]

Arpit Agarwal

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Informative Path Planning with Limited Adaptivity.

[BibT_eX]

[DOI]

Rayen Tan

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2024

2023

Efficient Algorithms for Stochastic Ride-Pooling Assignment with Mixed Fleets.

[BibT_eX]

[DOI]

Transp. Sci., July, 2023

Minimum Cost Adaptive Submodular Cover.

[BibT_eX]

[DOI]

Yubing Cui

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

2022

On some variants of Euclidean k-supplier.

[BibT_eX]

[DOI]

Euiwoong Lee

Lily Wang

Oper. Res. Lett., 2022

Stochastic makespan minimization in structured set systems.

[BibT_eX]

[DOI]

Math. Program., 2022

Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems.

[BibT_eX]

[DOI]

Math. Oper. Res., 2022

Constrained Assortment Optimization Under the Paired Combinatorial Logit Model.

[BibT_eX]

[DOI]

Oper. Res., 2022

Improving Column Generation for Vehicle Routing Problems via Random Coloring and Parallelization.

[BibT_eX]

[DOI]

Miao Yu

Siqian Shen

INFORMS J. Comput., 2022

An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem.

[BibT_eX]

[DOI]

Arpit Agarwal

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Non-adaptive Stochastic Score Classification and Explainable Halfspace Evaluation.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2022

Batched Dueling Bandits.

[BibT_eX]

[DOI]

Arpit Agarwal

Proceedings of the International Conference on Machine Learning, 2022

2021

Efficient Algorithms for Stochastic Ridepooling Assignment with Mixed Fleets.

[BibT_eX]

[DOI]

CoRR, 2021

Online Generalized Network Design Under (Dis)Economies of Scale.

[BibT_eX]

[DOI]

Lily Wang

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

The Power of Adaptivity for Stochastic Submodular Cover.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

2020

Approximation algorithms for the a priori traveling repairman.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2020

Online covering with ℓ q-norm objectives and applications to network design.

[BibT_eX]

[DOI]

Math. Program., 2020

The Euclidean k-Supplier Problem.

[BibT_eX]

[DOI]

Baruch Schieber

Hadas Shachnai

Math. Oper. Res., 2020

Adaptive Submodular Ranking and Routing.

[BibT_eX]

[DOI]

Prabhanjan Kambadur

Oper. Res., 2020

Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2020

2019

Malleable scheduling for flows of jobs and applications to MapReduce.

[BibT_eX]

[DOI]

J. Sched., 2019

Approximation Algorithms for the A Priori TravelingRepairman.

[BibT_eX]

[DOI]

CoRR, 2019

Optimal Decision Tree with Noisy Outcomes.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

2018

An approximation algorithm for vehicle routing with compatibility constraints.

[BibT_eX]

[DOI]

Miao Yu

Siqian Shen

Oper. Res. Lett., 2018

Approximating max-cut under graph-MSO constraints.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2018

Approximating graph-constrained max-cut.

[BibT_eX]

[DOI]

Jon Lee

Math. Program., 2018

A Quasi-Polynomial Algorithm for Submodular Tree Orienteering in Directed Graphs.

[BibT_eX]

[DOI]

CoRR, 2018

Stochastic Load Balancing on Unrelated Machines.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions.

[BibT_eX]

[DOI]

Sahil Singla

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Adaptive Submodular Ranking.

[BibT_eX]

[DOI]

Prabhanjan Kambadur

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Online Covering with Sum of $ell_q$-Norm Objectives.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Approximation Algorithms for Stochastic k-TSP.

[BibT_eX]

[DOI]

Alina Ene

Rishi Saket

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

Minimum Makespan Vehicle Routing Problem with Compatibility Constraints.

[BibT_eX]

[DOI]

Miao Yu

Siqian Shen

Proceedings of the Integration of AI and OR Techniques in Constraint Programming, 2017

2016

Stochastic Knapsack.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Approximation algorithms for inventory problems with submodular or routing costs.

[BibT_eX]

[DOI]

Cong Shi

Math. Program., 2016

Capacitated Vehicle Routing with Nonuniform Speeds.

[BibT_eX]

[DOI]

Math. Oper. Res., 2016

Algorithms and Adaptivity Gaps for Stochastic Probing.

[BibT_eX]

[DOI]

Sahil Singla

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Max-Cut Under Graph Constraints.

[BibT_eX]

[DOI]

Jon Lee

Proceedings of the Integer Programming and Combinatorial Optimization, 2016

Approximation-Friendly Discrepancy Rounding.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2016

Online Algorithms for Covering and Packing Problems with Convex Objectives.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Facility Location with Matroid or Knapsack Constraints.

[BibT_eX]

[DOI]

Math. Oper. Res., 2015

Running Errands in Time: Approximation Algorithms for Stochastic Orienteering.

[BibT_eX]

[DOI]

Math. Oper. Res., 2015

The Container Selection Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2014

Online Packing and Covering Framework with Convex Objectives.

[BibT_eX]

[DOI]

CoRR, 2014

Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing.

[BibT_eX]

[DOI]

Kirk Pruhs

Cliff Stein

Proceedings of the Symposium on Theory of Computing, 2014

Hallucination Helps: Energy Efficient Virtual Circuit Routing.

[BibT_eX]

[DOI]

Antonios Antoniadis

Sungjin Im

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

The X-flex cross-platform scheduler: who's the fairest of them all?

[BibT_eX]

[DOI]

Proceedings of the Middleware Industry Track, Bordeaux, France, December 8-12, 2014, 2014

On the Adaptivity Gap of Stochastic Orienteering.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2014

2013

FlowFlex: Malleable Scheduling for Flows of MapReduce Jobs.

[BibT_eX]

[DOI]

Proceedings of the Middleware 2013, 2013

The Euclidean k-Supplier Problem.

[BibT_eX]

[DOI]

Baruch Schieber

Hadas Shachnai

Proceedings of the Integer Programming and Combinatorial Optimization, 2013

Thrifty Algorithms for Multistage Robust Optimization.

[BibT_eX]

[DOI]

Vijay V. Vazirani

Proceedings of the Integer Programming and Combinatorial Optimization, 2013

A Stochastic Probing Problem with Applications.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2013

Algorithms for Hub Label Optimization.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

The Approximability of the Binary Paintshop Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Solving Packing Integer Programs via Randomized Rounding with Alterations.

[BibT_eX]

[DOI]

Theory Comput., 2012

Approximation algorithms for distance constrained vehicle routing problems.

[BibT_eX]

[DOI]

Networks, 2012

Technical Note - Approximation Algorithms for VRP with Stochastic Demands.

[BibT_eX]

[DOI]

Oper. Res., 2012

When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings.

[BibT_eX]

[DOI]

Algorithmica, 2012

Approximation algorithms for stochastic orienteering.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Multicast Routing for Energy Minimization Using Speed Scaling.

[BibT_eX]

[DOI]

Kirk Pruhs

Cliff Stein

Proceedings of the Design and Analysis of Algorithms, 2012

Minimum Latency Submodular Cover.

[BibT_eX]

[DOI]

Sungjin Im

Ruben van der Zwaan

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Approximating Sparse Covering Integer Programs Online.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Stochastic Vehicle Routing with Recourse.

[BibT_eX]

[DOI]

Rishi Saket

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Minimum Latency Submodular Cover in Metrics

[BibT_eX]

[DOI]

Sungjin Im

CoRR, 2011

The Directed Orienteering Problem.

[BibT_eX]

[DOI]

Algorithmica, 2011

The Matroid Median Problem.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Minimum congestion mapping in a cloud.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

Capacitated Vehicle Routing with Non-uniform Speeds.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatoral Optimization, 2011

Min-max Graph Partitioning and Small Set Expansion.

[BibT_eX]

[DOI]

Uriel Feige

Robert Krauthgamer

Konstantin Makarychev

Joseph Naor

Roy Schwartz

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Locating Depots for Capacitated Vehicle Routing.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2010

Simpler analysis of LP extreme points for traveling salesman and survivable network design problems.

[BibT_eX]

[DOI]

Mohit Singh

Oper. Res. Lett., 2010

An improved approximation algorithm for requirement cut.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2010

A Plant Location Guide for the Unsure: Approximation Algorithms for Min-Max Location Problems.

[BibT_eX]

[DOI]

Math. Oper. Res., 2010

Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems

[BibT_eX]

[DOI]

CoRR, 2010

On k-Column Sparse Packing Programs.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

On Generalizations of Network Design Problems with Degree Bounds.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Thresholded Covering Algorithms for Robust and Max-min Optimization.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Better Scalable Algorithms for Broadcast Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2010

2009

On k-Column Sparse Packing Programs

[BibT_eX]

[DOI]

Nitish Korula

CoRR, 2009

Non-monotone submodular maximization under matroid and knapsack constraints.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

On the maximum quadratic assignment problem.

[BibT_eX]

[DOI]

Maxim Sviridenko

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Minimum Makespan Multi-vehicle Dial-a-Ride.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2009

2008

On the LP Relaxation of the Asymmetric Traveling Salesman Path Problem.

[BibT_eX]

[DOI]

Theory Comput., 2008

Exact train pathing.

[BibT_eX]

[DOI]

Abhiram G. Ranade

J. Sched., 2008

Additive guarantees for degree bounded directed network design.

[BibT_eX]

[DOI]

Rohit Khandekar

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

A plant location guide for the unsure.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Tight Bounds for Permutation Flow Shop Scheduling.

[BibT_eX]

[DOI]

Maxim Sviridenko

Proceedings of the Integer Programming and Combinatorial Optimization, 2008

The Directed Minimum Latency Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2008

2007

Dial a Ride from k-forest

[BibT_eX]

[DOI]

MohammadTaghi Hajiaghayi

CoRR, 2007

Dial a Ride from k -Forest.

[BibT_eX]

[DOI]

MohammadTaghi Hajiaghayi

Proceedings of the Algorithms, 2007

Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2007

2006

Approximating the k-multicut problem.

[BibT_eX]

[DOI]

Daniel Golovin

Mohit Singh

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Minimum Vehicle Routing with a Common Deadline.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2006

2005

Fairness and optimality in congestion games.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Aranyak Mehta

Proceedings of the Proceedings 6th ACM Conference on Electronic Commerce (EC-2005), 2005

Approximation Algorithms for Requirement Cut on Graphs.

[BibT_eX]

[DOI]