Author name cluster

James B. Orlin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

14 papers

1 author row

SODA Conference 2021 Conference Paper

Directed Shortest Paths via Approximate Cost Balancing

James B. Orlin
László A. Végh

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.

Details

SODA Conference 2017 Conference Paper

An O ( nm ) time algorithm for finding the min length directed cycle in a graph

James B. Orlin
Antonio Sedeño-Noda

In this paper, we introduce an O ( nm ) time algorithm to determine the minimum length directed cycle (also called the “minimum weight directed cycle”) in a directed network with n nodes and m arcs and with no negative length directed cycles. This result improves upon the previous best time bound of O ( nm + n 2 log log n ). Our algorithm first determines the cycle with minimum mean length λ* in O ( nm ) time. Subsequently, it chooses node potentials so that all reduced costs are λ* or greater. It then solves the all pairs shortest path problem, but restricts attention to paths of length at most n λ *. We speed up the shortest path calculations to O ( m ) per source node, leading to an O ( nm ) running time in total. We also carry out computational experiments comparing the performance of the proposed methods and other state-of-the-art methods. Experiments confirmed that it is advantageous to solve the minimum mean cycle problem prior to solving shortest path problems. Analysis of our experiments suggest that the running time to solve the minimum length directed cycle problem was much faster than O ( n 2 ) on average.

Details

STOC Conference 2013 Conference Paper

Max flows in O(nm) time, or better

James B. Orlin

In this paper, we present improved polynomial time algorithms for the max flow problem defined on sparse networks with n nodes and m arcs. We show how to solve the max flow problem in O(nm + m 31/16 log 2 n) time. In the case that m = O(n 1.06 ), this improves upon the best previous algorithm due to King, Rao, and Tarjan, who solved the max flow problem in O(nm log m/(n log n) n) time. This establishes that the max flow problem is solvable in O(nm) time for all values of n and m. In the case that m = O(n), we improve the running time to O(n 2 / log n).

Details

STOC Conference 2010 Conference Paper

Improved algorithms for computing fisher's market clearing prices: computing fisher's market clearing prices

James B. Orlin

We give the first strongly polynomial time algorithm for computing an equilibrium for the linear utilities case of Fisher's market model. We consider a problem with a set B of buyers and a set G of divisible goods. Each buyer i starts with an initial integral allocation e i of money. The integral utility for buyer i of good j is U ij . We first develop a weakly polynomial time algorithm that runs in O(n 4 log U max + n 3 e max ) time, where n = |B| + |G|. We further modify the algorithm so that it runs in O(n 4 log n) time. These algorithms improve upon the previous best running time of O(n 8 log U max + n 7 log e max ), due to Devanur et al.

Details

SODA Conference 2009 Conference Paper

A simple combinatorial algorithm for submodular function minimization

Satoru Iwata 0001
James B. Orlin

This paper presents a new simple algorithm for minimizing submodular functions. For integer valued submodular functions, the algorithm runs in O ( n 6 EO log nM ) time, where n is the cardinality of the ground set, M is the maximum absolute value of the function value, and EO is the time for function evaluation. The algorithm can be improved to run in O (( n 4 EO + n 5 ) log nM ) time. The strongly polynomial version of this faster algorithm runs in O (( n 5 EO + n 6 ) log n ) time for real valued general submodular functions. These are comparable to the best known running time bounds for submodular function minimization. The algorithm can also be implemented in strongly polynomial time using only additions, subtractions, comparisons, and the oracle calls for function evaluation. This is the first fully combinatorial submodular function minimization algorithm that does not rely on the scaling method.

Details

SODA Conference 2008 Conference Paper