Arrow Research search

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

Possible papers

14

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

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