James B. Orlin

James B. Orlin

Auto-generated profile, based on publicly available information

James B. Orlin

University of Wisconsin Georgetown MSB and AEI UC Berkeley MIT Sloan

Research Focus & Metrics

Academic Career Length

50Years (1977-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 November 2002 in Discrete Applied Mathematics
Verified
Journal Article
Closed access
RARavindra K. Ahuja
Ravindra K. Ahuja
ÖEÖzlem Ergun
Özlem Ergun
JOJames B. Orlin
James B. Orlin
APAbraham P. Punnen
Abraham P. Punnen

1 April 1993 in Operations Research
Verified
Journal Article
Closed access
JOJames B. Orlin
James B. Orlin
In this paper, we present a new strongly polynomial time algorithm for the minimum cost flow problem, based on a refinement of the Edmonds-Karp scaling technique. Our algorithm solves the uncapacitated minimum cost flow problem as a sequence of O(n log n) shortest path problems on networks with n nodes and m arcs and runs in O(n log n(m + n log n)) time. Using a standard transformation, this approach yields an O(m log n(m + n log n)) algorithm for the capacitated minimum cost flow problem. This algorithm improves the best previous strongly polynomial time algorithm, due to Z. Galil and E. Tardos, by a factor of n2/m. Our algorithm for the capacitated minimum cost flow problem is even more efficient if the number of arcs with finite upper bounds, say m′, is much less than m. In this case, the running time of the algorithm is O((m′ + n) log n(m + n log n)).

1 April 1990 in Journal of the ACM
Verified
Journal Article
Open access
RARavindra K. Ahuja
Ravindra K. Ahuja
KMKurt Mehlhorn
Kurt Mehlhorn
JOJames Orlin
James Orlin
RTRobert E. Tarjan
Robert E. Tarjan
Efficient implementations of Dijkstra's shortest path algorithm are investigated. A new data structure, called the radix heap , is proposed for use in this algorithm. On a network with n vertices, m edges, and nonnegative integer arc costs bounded by C , a one-level form of radix heap gives a time bound for Dijkstra's algorithm of O ( m + n log C ). A two-level form of radix heap gives a bound of O ( m + n log C /log log C ). A combination of a radix heap and a previously known data structure called a Fibonacci heap gives a bound of O ( m + n a @@@@log C ). The best previously known bounds are O ( m + n log n ) using Fibonacci heaps alone and O ( m log log C ) using the priority queue structure of Van Emde Boas et al. [ 17].

1 October 2001 in Operations Research
Verified
Journal Article
Closed access
RARavindra K. Ahuja
Ravindra K. Ahuja
JOJames B. Orlin
James B. Orlin
In this paper, we study inverse optimization problems defined as follows. Let S denote the set of feasible solutions of an optimization problem P, let c be a specified cost vector, and x0 be a given feasible solution. The solution x0 may or may not be an optimal solution of P with respect to the cost vector c. The inverse optimization problem is to perturb the cost vector c to d so that x0 is an optimal solution of P with respect to d and ‖d−c‖p is minimum, where ‖d−c‖p is some selected Lp norm. In this paper, we consider the inverse linear programming problem under L1 norm (where ‖d−c‖p = Σi∈J wj|dj−cj|, with J denoting the index set of variables xj and wj denoting the weight of the variable j) and under L∞ norm (where ‖d−c‖p = maxj∈J{wj|dj−cj|}). We prove the following results: (i) If the problem P is a linear programming problem, then its inverse problem under the L1 as well as L∞ norm is also a linear programming problem. (ii) If the problem P is a shortest path, assignment or minimum cut problem, then its inverse problem under the L1 norm and unit weights can be solved by solving a problem of the same kind. For the nonunit weight case, the inverse problem reduces to solving a minimum cost flow problem. (iii) If the problem P is a minimum cost flow problem, then its inverse problem under the L1 norm and unit weights reduces to solving a unit-capacity minimum cost flow problem. For the nonunit weight case, the inverse problem reduces to solving a minimum cost flow problem. (iv) If the problem P is a minimum cost flow problem, then its inverse problem under the L∞ norm and unit weights reduces to solving a minimum mean cycle problem. For the nonunit weight case, the inverse problem reduces to solving a minimum cost-to-time ratio cycle problem. (v) If the problem P is polynomially solvable for linear cost functions, then inverse versions of P under the L1 and L∞ norms are also polynomially solvable.

1 August 1997 in Mathematical Programming
Verified
Journal Article
Closed access
PDF file
JOJames B. Orlin
James B. Orlin

1 September 2000 in Computers & Operations Research
Verified
Journal Article
Closed access
RARavindra K. Ahuja
Ravindra K. Ahuja
JOJames B. Orlin
James B. Orlin
ATAshish Tiwari
Ashish Tiwari