186 citations · 243 across the 8 of their papers we have counts for
10 papers
Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
Christoph Grüne, Berit Johannes, James B. Orlin +1
Many natural optimization problems derived from admit bilevel and multilevel extensions in which decisions are made sequentially by multiple players with conflicting objec…
From Incremental Transitive Cover to Strongly Polynomial Maximum Flow
Daniel Dadush, James B. Orlin, Aaron Sidford +1
We provide faster strongly polynomial time algorithms solving maximum flow in structured -node -arc networks. Our results imply an -time strongly polynomial time…
The Strong Maximum Circulation Algorithm: A New Method for Aggregating Preference Rankings
Nathan Atkinson, Scott C. Ganz, Dorit S. Hochbaum +1
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…
Directed Shortest Paths via Approximate Cost Balancing
James B. Orlin, László A. Végh
We present an algorithm for all-pairs shortest paths computations in a directed graph with nodes, arcs, and nonnegative integer arc costs. This matches the complexi…
A Fast Max Flow Algorithm
James B. Orlin, Xiao-Yue Gong
In 2013, Orlin proved that the max flow problem could be solved in time. His algorithm ran in time, which was the fastest for graphs with fewer than $n^{…
Robust Monotone Submodular Function Maximization
James B. Orlin, Andreas S. Schulz, Rajan Udwani
We consider a robust formulation, introduced by Krause et al. (2008), of the classical cardinality constrained monotone submodular function maximization problem, and give the first…