About

James B. Orlin is the E. Pennell Brooks (1917) Professor in Management and a Professor of Operations Research at the MIT Sloan School of Management. He specializes in network and combinatorial optimization, contributing to the development of improved solution methodologies in airline scheduling, railroad scheduling, logistics, network design, telecommunications, inventory control, and marketing. Orlin has co-authored the award-winning textbook, Network Flows: Theory, Algorithms, and Applications, and holds degrees in mathematics from the University of Pennsylvania and the California Institute of Technology, a MMath from the University of Waterloo, and a PhD in operations research from Stanford University. His work has been recognized with prestigious awards such as the 2020 INFORMS Khachiyan Prize for lifetime achievements in optimization, and the ACM SIGecom Test of Time Award for impactful research in computational social choice. His research and contributions have significantly advanced the fields of network flows and combinatorial optimization.

Research topics

• Computer Science
• Algorithm
• Mathematics
• Combinatorics
• Theoretical computer science

Selected publications

• Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP

  Open MIND · 2026-02-12

  preprint

  Many natural optimization problems derived from $\sf NP$ admit bilevel and multilevel extensions in which decisions are made sequentially by multiple players with conflicting objectives, as in interdiction, adversarial selection, and adjustable robust optimization. Such problems are naturally modeled by alternating quantifiers and, therefore, lie beyond $\sf NP$, typically in the polynomial hierarchy or $\sf PSPACE$. Despite extensive study of these problem classes, relatively few natural completeness results are known at these higher levels. We introduce a general framework for proving completeness in the polynomial hierarchy and $\sf PSPACE$ for problems derived from $\sf NP$. Our approach is based on a refinement of $\sf NP$, which we call $\sf NP$ with solutions ($\sf NP$-$\sf S$), in which solutions are explicit combinatorial objects, together with a restricted class of reductions -- solution-embedding reductions -- that preserve solution structure. We define $\sf NP$-$\sf S$-completeness and show that a large collection of classical $\sf NP$-complete problems, including Clique, Vertex Cover, Knapsack, and Traveling Salesman, are $\sf NP$-$\sf S$-complete. Using this framework, we establish general meta-theorems showing that if a problem is $\sf NP$-$\sf S$-complete, then its natural two-level extensions are $Σ_2^p$-complete, its three-level extensions are $Σ_3^p$-complete, and its $k$-level extensions are $Σ_k^p$-complete. When the number of levels is unbounded, the resulting problems are $\sf PSPACE$-complete. Our results subsume nearly all previously known completeness results for multilevel optimization problems derived from $\sf NP$ and yield many new ones simultaneously, demonstrating that high computational complexity is a generic feature of multilevel extensions of $\sf NP$-complete problems.

  DOI

• Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP

  arXiv (Cornell University) · 2026-02-12

  articleOpen access

  Many natural optimization problems derived from $\sf NP$ admit bilevel and multilevel extensions in which decisions are made sequentially by multiple players with conflicting objectives, as in interdiction, adversarial selection, and adjustable robust optimization. Such problems are naturally modeled by alternating quantifiers and, therefore, lie beyond $\sf NP$, typically in the polynomial hierarchy or $\sf PSPACE$. Despite extensive study of these problem classes, relatively few natural completeness results are known at these higher levels. We introduce a general framework for proving completeness in the polynomial hierarchy and $\sf PSPACE$ for problems derived from $\sf NP$. Our approach is based on a refinement of $\sf NP$, which we call $\sf NP$ with solutions ($\sf NP$-$\sf S$), in which solutions are explicit combinatorial objects, together with a restricted class of reductions -- solution-embedding reductions -- that preserve solution structure. We define $\sf NP$-$\sf S$-completeness and show that a large collection of classical $\sf NP$-complete problems, including Clique, Vertex Cover, Knapsack, and Traveling Salesman, are $\sf NP$-$\sf S$-complete. Using this framework, we establish general meta-theorems showing that if a problem is $\sf NP$-$\sf S$-complete, then its natural two-level extensions are $Σ_2^p$-complete, its three-level extensions are $Σ_3^p$-complete, and its $k$-level extensions are $Σ_k^p$-complete. When the number of levels is unbounded, the resulting problems are $\sf PSPACE$-complete. Our results subsume nearly all previously known completeness results for multilevel optimization problems derived from $\sf NP$ and yield many new ones simultaneously, demonstrating that high computational complexity is a generic feature of multilevel extensions of $\sf NP$-complete problems.

  PublisherOA PDF

• From Incremental Transitive Cover to Strongly Polynomial Maximum Flow

  Society for Industrial and Applied Mathematics eBooks · 2026-01-01

  book-chapter

  We provide faster strongly polynomial time algorithms solving maximum flow in structured \(n\)-node \(m\)-arc networks. Our results imply an \(n^{\omega+o(1)}\)-time strongly polynomial time algorithms for computing a maximum bipartite \(b\)-matching where \(\omega\) is the matrix multiplication constant. Additionally, they imply an \(m^{1+o(1)}W\)-time algorithm for solving the problem on graphs with a given tree decomposition of width \(W\).

  PublisherDOI

• From Incremental Transitive Cover to Strongly Polynomial Maximum Flow

  ArXiv.org · 2025-10-23

  preprintOpen access

  We provide faster strongly polynomial time algorithms solving maximum flow in structured $n$-node $m$-arc networks. Our results imply an $n^{ω+ o(1)}$-time strongly polynomial time algorithms for computing a maximum bipartite $b$-matching where $ω$ is the matrix multiplication constant. Additionally, they imply an $m^{1 + o(1)} W$-time algorithm for solving the problem on graphs with a given tree decomposition of width $W$. We obtain these results by strengthening and efficiently implementing an approach in Orlin's (STOC 2013) state-of-the-art $O(mn)$ time maximum flow algorithm. We develop a general framework that reduces solving maximum flow with arbitrary capacities to (1) solving a sequence of maximum flow problems with polynomial bounded capacities and (2) dynamically maintaining a size-bounded supersets of the transitive closure under arc additions; we call this problem \emph{incremental transitive cover}. Our applications follow by leveraging recent weakly polynomial, almost linear time algorithms for maximum flow due to Chen, Kyng, Liu, Peng, Gutenberg, Sachdeva (FOCS 2022) and Brand, Chen, Kyng, Liu, Peng, Gutenberg, Sachdeva, Sidford (FOCS 2023), and by developing incremental transitive cover data structures.

  PublisherOA PDFDOI

• The Strong Maximum Circulation Algorithm: A New Method for Aggregating Preference Rankings

  INFORMS Journal on Optimization · 2025-02-28

  articleOpen accessSenior author

  We present a new optimization-based method for aggregating preferences in settings in which each voter expresses preferences over pairs of alternatives. Our approach to identifying a consensus partial order is motivated by the observation that collections of votes that form a cycle can be treated as collective ties. Our approach then removes unions of cycles of votes, or circulations, from the vote graph and determines aggregate preferences from the remainder. Specifically, we study the removal of maximal circulations attained by any union of cycles the removal of which leaves an acyclic graph. We introduce the strong maximum circulation, the removal of which guarantees a unique outcome in terms of the induced partial order, called the strong partial order. The strong maximum circulation also satisfies strong complementary slackness conditions and is shown to be solved efficiently as a network flow problem. We further establish the relationship between the dual of the maximum circulation problem and Kemeny’s method, a popular optimization-based approach for preference aggregation. We also show that identifying a minimum maximal circulation—that is, a maximal circulation containing the smallest number of votes—is an NP-hard problem. Further, an instance of the minimum maximal circulation may have multiple optimal solutions whose removal results in conflicting partial orders. Funding: D. Hochbaum’s research is supported in part by AI institute National Science Foundation award 2112533.

  PublisherDOI

• FOREWORD TO THE 2010 EDITION

  Princeton University Press eBooks · 2024-12-03

  book-chapterSenior author
  PublisherDOI

• The Strong Maximum Circulation Algorithm: A New Method for Aggregating Preference Rankings

  arXiv (Cornell University) · 2023-07-28 · 1 citations

  preprintOpen accessSenior author

  We present a new optimization-based method for aggregating preferences in settings where each voter expresses preferences over pairs of alternatives. Our approach to identifying a consensus partial order is motivated by the observation that collections of votes that form a cycle can be treated as collective ties. Our approach then removes unions of cycles of votes, or circulations, from the vote graph and determines aggregate preferences from the remainder. Specifically, we study the removal of maximal circulations attained by any union of cycles the removal of which leaves an acyclic graph. We introduce the strong maximum circulation, the removal of which guarantees a unique outcome in terms of the induced partial order, called the strong partial order. The strong maximum circulation also satisfies strong complementary slackness conditions, and is shown to be solved efficiently as a network flow problem. We further establish the relationship between the dual of the maximum circulation problem and Kemeny's method, a popular optimization-based approach for preference aggregation. We also show that identifying a minimum maximal circulation -- i.e., a maximal circulation containing the smallest number of votes -- is an NP-hard problem. Further an instance of the minimum maximal circulation may have multiple optimal solutions whose removal results in conflicting partial orders.

  PublisherOA PDFDOI

• Directed Shortest Paths via Approximate Cost Balancing

  Society for Industrial and Applied Mathematics eBooks · 2021-01-01

  preprintOpen access1st authorCorresponding

  We present an O(nm) algorithm for all-pairs shortest paths computations in a directed graph with n nodes, m arcs, and nonnegative integer arc costs. This matches the complexity bound attained by Thorup [26] for the all-pairs problems in undirected graphs. Our main insight is that shortest paths problems with approximately balanced directed cost functions can be solved similarly to the undirected case. Our algorithm starts with an preprocessing step that finds a 3-min-balanced reduced cost function. Using these reduced costs, every shortest path query can be solved in O(m) time using an adaptation of Thorup's component hierarchy method. The balancing result is of independent interest, and gives the best currently known approximate balancing algorithm for the problem.

  PublisherOA PDFDOI

• Linearizable Special Cases of the Quadratic Shortest Path Problem

  Lecture notes in computer science · 2021 · 3 citations

  • Computer Science
  • Computer Science
  • Mathematics
  PublisherDOI

• A fast maximum flow algorithm

  Networks · 2020 · 8 citations

  1st authorCorresponding
  • Computer Science
  • Algorithm
  • Mathematics

  Abstract In 2013, Orlin proved that the max flow problem could be solved in O ( nm ) time. His algorithm ran in O ( nm + m 1.94 ) time, which was the fastest for graphs with fewer than n 1.06 arcs. If the graph was not sufficiently sparse, the fastest running time was an algorithm due to King, Rao, and Tarjan. We describe a new variant of the excess scaling algorithm for the max flow problem whose running time strictly dominates the running time of the algorithm by King et al. For graphs in which m = O ( n log n ) , the running time of our algorithm dominates that of King et al. by a factor of O (loglog n ) . Moreover, our algorithm achieves this improved performance without reliance on dynamic trees.

  PublisherOA PDFDOI

Recent grants

• Nearly Optimal Solutions for Stochastic Optimization Problems

  NSF · $339k · 2008–2012

• Hub Based Routing of Highly Variable Traffic

  NSF · $59k · 2005–2007

• A Grammar-Based Approach to Dynamic Programming for Combinatorial Optimization

  NSF · $110k · 2006–2008

Frequent coauthors

• Ravindra K. Ahuja

  86 shared

• Dushyant Sharma

  16 shared

• Nir Halman

  13 shared

• Thomas L. Magnanti

  Singapore University of Technology and Design

  12 shared

• László A. Végh

  London School of Economics and Political Science

  12 shared

• Özlem Ergün

  Northeastern University

  11 shared

• David Simchi‐Levi

  10 shared

• Andreas S. Schulz

  9 shared

Education

• Ph.D., Operations Research

  Stanford University

  1981

• MMath, Combinatorics and Optimization

  University of Waterloo

  1976

• M.S., Mathematics

  California Institute of Technology

  1976

• BA, Mathematics

  University of Pennsylvania

  1974

Awards & honors

• Khachiyan Prize (2020) INFORMS Optimization Society
• Test of Time Award ACM SIGecom
• Leonard G. Abraham Prize in Communications (year not specifi…