ARTICLE An STS-Based Map of the Human Genome (2008)
Thomas J. Hudson, Lincoln D. Stein, Sebastian S. Gerety, Junli Ma, Andrew B. Castle, ...
A physical map has been constructed of the human genome containing 15,086 sequence-tagged sites (STSs), with an average spacing of 199 kilobases. The project involved assembly of a radiation hybrid...
Computer Algorithms. Addison-Wesley, 1974. (2008)
Milton Abramowitz, Irene A. Stegun, Leonard M. Adleman, Carl Pomerance, ...
numbers from composite numbers. Annals of Mathematics, 117:173–206, 1983. [4] Alok Aggarwal and Jeffrey Scott Vitter. The input/output complexity of sorting and related problems. Communications of...
References Constrained Model–Based Clustering (2008)
Gunter Ritter, Hans Achatz, Peter Kleinschmidt, Bernd Sturmfels, Ravindra K. Ahuja, ...
algorithms for bipartite network flows. SIAM J. Computing, 23:906–933, 1994. [3] María Teresa Gallegos and Gunter Ritter. A robust method for cluster analysis. Annals
On Geometric Stable Roommates and Minimum-Weight Matching Robustness (Extended Abstract) ∗ (2008)
Valentin Polishchuk, Esther M. Arkin, Kobus Barnard, Kevin Coogan, Alon Efrat, ...
Abstract This paper consists of two parts, both of which address stability of perfect matchings. In the first part we consider instances of the Stable Roommates problem that arise from geometric...
James B. Orlin, John Vandevate
Given two matroids M 1 = (S, 1 1) and M 2 = (S, 12) and a weight function s on S, the weighted matroid intersection problem is to find a common independent set of maximum weight. In this paper, we...
Ravinda K. Ahuja, James B. Orlin, Stefano Pallottino, Maria G, Nikhil Bansal, Avrim Blum, ...
Scutella. Dynamic shortest paths minimizing travel times and costs. Networks,
1 The Extended Neighborhood (2008)
James B. Orlin, Dushyant Sharma, James B. Orlin, Dushyant Sharma
We consider neighborhood search defined on combinatorial optimization problems. Suppose that N is a neighborhood for combinatorial optimization problem X. We say that N ′ is LO-equivalent (locally...
VeryLarge-ScaleNeighborhood Search Techniques in Timetabling Problems (2008)
We describe the use ofvery large-scale neighborhood search techniques in examination timetabling problems. We detail three applications ofVLSN algorithms that illustrate the versatility and potential...
Algorithms New Polynomial-Time Cycle-Canceling Algorithms for Minimum Cost Flows (2008)
P. T. Sokkalingam, Ravindra K. Ahuja, James B. Orlin, P. T. Sokkalingam, Ravindra K. Ahuja, James B. Orlin, ...
The cycle-canceling algorithm is one of the earliest algorithms to solve the minimum cost flow problem. This algorithm maintains a feasible solution x in the network G and proceeds by augmenting...
Very Large-Scale Neighborhood Search Techniques in Timetabling Problems (2008)
Abstract. We describe the use of very large-scale neighborhood search (VLSN) techniques in examination timetabling problems. We detail three applications of VLSN algorithms that illustrate the...
4 On Multiroute Maximum Flows in Networks (2008)
Charu C. Aggarwal, James B. Orlin
Let G = (N, A) be a network with a designated source node s, a designated sink node t, and a finite integral capacity ui 1 on each arc (i, j) E A. An elementary K-flow is a flow of K units from s to...
Lexicographically Minimum and Maximum Load Linear Programming Problems (2008)
In this paper we introduce the lexicographically minimum load linear programming problem and we provide a polynomial approach followed by the proof of correctness. This problem has applications in...
Errata for Network Flows: Theory, Algorithms, and Applications. By (2008)
Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin
Errors listed in blue were corrected in the 4 th printing of the textbook. Errors listed in boldface black still remain as errors. I thank all of you who have sent me corrections over the years. If...
SOLVING MULTI-CRITERIA THROUGH-FLEET ASSIGNMENT MODELS (2008)
Ravindra K. Ahuja, Jian Liu, Jon Goodstein, Amit Mukherjee, James B. Orlin, Dushyant Sharma
Abstract The airline industry has been a pioneer in using operations research techniques to solve complex business problems related to the schedule planning of the airline. Given a flight schedule,...
Very Large-Scale Neighborhood Search (2008)
Techniques In Timetabling, Carol Meyers, James B. Orlin
We describe the use of very large-scale neighborhood search (VLSN) techniques in examination timetabling problems. We detail three applications of VLSN algorithms that illustrate the versatility and...
Parallel Algorithms for the Assignment and Minimum-Cost Flow Problems (2008)
James B. Orlin, Clifford Stein
Let G = (V; E) be a network for an assignment problem with 2n nodes and m edges, in which the largest edge cost is C. Recently the class of instances of bipartite matching problems has been shown to...
Errata for Network Flows: Theory, Algorithms, and Applications. By (2007)
Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin
Errors listed in blue were corrected in the 4 th printing of the textbook. Errors listed in boldface black still remain as errors. I thank all of you who have sent me corrections over the years. If...
Janos Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
In this paper we present a theoretical analysis of the deterministic on-line Sum of Squares algorithm (SS) for bin packing introduced and studied experimentally
A Network Simplex Algorithm with O(n) Consecutive Degenerate Pivots (2007)
Ravindra K. Ahuja, Ravindra K. Ahuja, James B. Orlin, James B. Orlin, Prabha Sharma, Prabha Sharma, ...
In this paper, we suggest a new pivot rule for the primal simplex algorithm for the minimum cost flow problem, known as the network simplex algorithm. Due to degeneracy, cycling may occur in the...
Optimal Rounding of Instantaneous Fractional Flows Over Time (2007)
Lisa K. Fleischer, James B. Orlin
A transshipment problem with demands that exceed network capacity can be solved by sending ow inseveral waves. How can this be done in the minimum number, T,ofwaves, and at minimum cost, if costs are...
Abstract On the Sum-of-Squares Algorithm for Bin Packing (2007)
Janos Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Cedex France
In this paper we present a theoretical analysis of the deterministic on-line Sum of Squares algorithm (SS) for bin packing, introduced and studied experimentally in [8], along with several new...
Motivated by the need to deal with imprecise data in realworld optimization problems, we introduce two new models for algorithm design and analysis. The rst model, called the L-bit precision model...
Abstract On Multi-route Maximum Flows in Networks (2007)
Charu C. Aggarwal, James B. Orlin
Let G =(N � A) be a network with a designated source node s, a designated sink node t, and a nite integral capacity uij on each arc (i � j) 2 A. An elementary K- ow isa owofK units from s to t...
INVERSE SPANNING TREE PROBLEMS: FORMULATIONS AND ALGORITHMS (2007)
P. T. Sokkalingam, P. T. Sokkalingam, Ravindra K. Ahuja, Ravindra K. Ahuja, James B. Orlin, James B. Orlin
Given a solution x * and an a priori estimated cost vector c, the inverse optimization problem is to identify another cost vector d so that x * is optimal with respect to the cost vector d and the...
School of Operations Research, (2007)
James B. Orlin, Serge A. Plotkin, Eva Tardos
We show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule. Our best pivoting strategy...
Neal E. Young, Robert E. Tarjan, James B. Orlin
We use Fibonacci heaps to improve a parametric shortest path algorithm of Karp and Orlin, and we combine our algorithm and the method of Schneider and Schneider's minimum-balance algorithm to...
A Capacity Scaling Algorithm for the Constrained Maximum Flow Problem (2007)
Ahuja, Ravindra K., Kanpur, I. I., Orlin, James B.
The constrained maximum flow problem is to send the maximum possible flow from a source node 5 to a sink node tin a directed network subject to a budget constraint that the cost of flow is no more...
Fast Approximation Schemes for Multi-Criteria Flow, Knapsack, and Scheduling Problems (2007)
Safer, Hershel M., Orlin, James B.
The solution to an instance of the standard Shortest Path problem is a single shortest route in a directed graph. Suppose, however, that each arc has both a distance and a cost, and that one would...
Parallel Algorithms for the Assignment and Minimum-Cost Flow Problems (2007)
Orlin, James B., Stein, Clifford
Let G = (V, E) be a network for an assignment problem with 2n nodes and m edges, in which the largest edge cost is C. Recently the class of instances of bipartite matching problems has been shown to...
A Technique for Speeding Up the Solution of the Lagrangean Dual (2007)
Bertsimas, Dimitris, Orlin, James B.
We propose new techniques for the solution of the LP relaxation and the Lagrangean dual in combinatorial optimization problems. Our techniques find the optimal solution value and the optimal dual...
Scheduling malleable tasks with interdependent processing rates: Comments and observations (2007)
Edmund K. Burke, Moshe Dror, James B. Orlin
In this short paper we examine the problem of scheduling malleable tasks on parallel processors. One of the main aims of the paper is to present a simple complexity interpretation for a number of...
Valentin Polishchuk, Esther M. Arkin, Kobus Barnard, Kevin Coogan, Alon Efrat, ...
We introduce the notion of robustness of the minimum-weight perfect matching. The robustness measures how much the edge weights of a graph are allowed to change before the minimum-weight matching...
A Faster Strongly Polynomial Minimum Cost Flow Algorithm (2006)
We present a new strongly polynomial 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...
A Faster Strongly Polynomial Minimum Cost Flow Algorithm (2006)
We present a new strongly polynomial 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...
Preconfiguring ip-over-optical networks to handle router failures and unpredictable traffic (2006)
M. Kodialam, T. V. Lakshman, James B. Orlin, Sudipta Sengupta
We consider the realization of traffic-oblivious routing in IP-over-Optical networks where routers are interconnected over a switched optical backbone. The traffic-oblivious routing we consider is a...
Improved Time Bounds for the Maximum Flow Problem, (2005)
Ahuma, Ravindra K., Orlin, James B., Tarjan, Robert E.
A new approach is proposed to the maximum network flow problem. The approach yields a very simple algorithm running O(n-cubed) time on n-vertex networks. Incorporation of the dynamic tree data...
Scale-invariant Clustering with Minimum Volume Ellipsoids (2005)
Mahesh Kumar, James B. Orlin, Mahesh Kumar, James B. Orlin
R u t c o r
Randal E. Hickman, F Technology, Margaret F. Nervegna, Charles Stark, Draper Laboratory, John N. Tsitsiklis, ...
hAr\r\r I I TI · 1 rl · ·. r
Ramkumar Ramaswamy, James B. Orlin, Nilopal Chakravarti
Abstract. Let G = (N,A) be an undirected graph with n nodes and m arcs, a designated source node s and a sink node t. This paper addresses sensitivity analysis questions concerning the shortest s-t...
Three Essays on Sequencing and Routing Problems (2005)
Agustfn Bompadre, James B. Orlin, John N. Tsitsiklis, Agustin Bompadre
2
Ramkumar Ramaswamy, James B. Orlin, Nilopal Chakravarti
Abstract. Let G = (N, A) be an undirected graph with n nodes and m arcs, a designated source node s and a sink node t. This paper addresses sensitivity analysis questions concerning the shortest s-t...
Nilopal Chakravarty, Ramkumar Ramaswamy, Ramkumar Ramaswamy, James B. Orlin, James B. Orlin, Nilopal Chakravarti
Short sections of text, not to exceed two paragraphs, may be quoted without explicit
Extended neighborhood: Definition and characterization (2004)
Orlin, James B., Sharma, Dushyant
We consider neighborhood search defined on combinatorial optimization problems. Suppose that N is a Neighborhood for combinatorial optimization problem X . We say that N ′ is LO-equivalent (locally...
Ramaswamy, Ramkumar, Orlin, James B., Chakravarty, Nilopal
This paper addresses sensitivity analysis questions concerning the shortest path problem and the maximum capacity path problem in an undirected network. For both problems, we determine the maximum...
Ramaswamy, Ramkumar, Orlin, James B., Chakravarty, Nilopal
This paper addresses sensitivity analysis questions concerning the shortest path problem and the maximum capacity path problem in an undirected network. For both problems, we determine the maximum...
We provide two different neighborhood construction techniques for creating exponentially large neighborhoods that are searchable in polynomial time using dynamic programming. We illustrate both of...
Exact and Heuristic Methods for the Weapon Target Assignment Problem (2004)
Ahuja, Ravindra K., Kumar, Arvind, Jha, Krishna, Orlin, James B.
The Weapon Target Assignment (WTA) problem is a fundamental problem arising in defense-related applications of operations research. This problem consists of optimally assigning n weapons to m targets...
Exact and Heuristic Methods for the Weapon Target Assignment Problem (2004)
Ahuja, Ravindra K., Kumar, Arvind, Jha, Krishna, Orlin, James B.
The Weapon Target Assignment (WTA) problem is a fundamental problem arising in defense-related applications of operations research. This problem consists of optimally assigning n weapons to m targets...
We provide two different neighborhood construction techniques for creating exponentially large neighborhoods that are searchable in polynomial time using dynamic programming. We illustrate both of...
The Metric TSP and the Sum of its Marginal Values (2004)
Moshe Dror, Yusin Lee, James B. Orlin, Valentin Polishchuk
This paper introduces a new notion related to the traveling salesperson problem (TSP) — the notion of the TSP ratio. The TSP ratio of a TSP instance I is the sum of the marginal values of the nodes...
Most successful heuristics for solving 1| | � wjTj are based on swap moves. We present an algorithm which improves the complexity of searching the swap neighborhood from O(n 3) to O(n 2). We show...
Packing Shelves with Divisible Items (2004)
Moshe Dror, James B. Orlin, Michael Zhu
In this paper we examine the issue of how likely it is that one can pack two shelves of integer length L by items whose individual lengths are divisors of L, given that the individual items sum-up to...
Solving parallel machine scheduling problems with variable depth local search (2004)
Richa Agarwal, Özlem Ergun, James B. Orlin, Chris N. Potts
We present new local search heuristic for the parallel machine total weighted completion time scheduling problem. Our algorithm is a local search method based on combining a variable number of...
Approximate local search in combinatorial optimization (2004)
Andreas S. Schulz, James B. Orlin, James B. Orlin, Abraham P. Punnen, Abraham P. Punnen, ...
Short sections of text, not to exceed two paragraphs, may be quoted without
Approximate local search in combinatorial optimization (2004)
James B. Orlin, Abraham P. Punnen, S. Schulz
Abstract. Local search algorithms for combinatorial optimization problems are generally of pseudopolynomial running time, and polynomial-time algorithms are not often known for finding locally...
Approximate local search in combinatorial optimization (2004)
Andreas S. Schulz, James B. Orlin, James B. Orlin, Abraham P. Punnen, Abraham P. Punnen, ...
Short sections of text, not to exceed two paragraphs, may be quoted without
Approximate Local Search in Combinatorial Optimization (2003)
Orlin, James B., Punnen, Abraham P., Schulz, Andreas S.
Local search algorithms for combinatorial optimization problems are in general of pseudopolynomial running time and polynomial-time algorithms are often not known for finding locally optimal...
Approximate Local Search in Combinatorial Optimization (2003)
Orlin, James B., Punnen, Abraham P., Schulz, Andreas S.
Local search algorithms for combinatorial optimization problems are in general of pseudopolynomial running time and polynomial-time algorithms are often not known for finding locally optimal...
Dynamic shortest paths minimizing travel times and costs (2003)
Ravindra K. Ahuja, James B. Orlin, Stefano Pallottino, Maria G. Scutellà
Dynamic Shortest Paths Minimizing Travel Times and Costs In this paper, we study dynamic shortest path problems, which is to determine a shortest path from a specified source node to every other node...
We provide two different neighborhood construction techniques for creating exponentially large neighborhoods that are searchable in polynomial time using dynamic programming. We illustrate both of...
Özlem Ergun, James B. Orlin, Abran Steele-feldman
Neighborhood search algorithms are a wide class of improvement algorithms where at each iteration an improving solution is found by searching the “neighborhood ” of the current solution. This...
Dynamic shortest paths minimizing travel times and costs (2003)
Ravindra K. Ahuja, James B. Orlin, Stefano Pallottino, Maria G. Scutellà
Dynamic Shortest Paths Minimizing Travel Times and Costs In this paper, we study dynamic shortest path problems that determine a shortest path from a specified source node to every other node in the...
Özlem Ergun, Özlem Ergun, James B. Orlin, James B. Orlin
Short sections of text, not to exceed two paragraphs, may be quoted without explicit
On the Sum-of-Squares Algorithm for Bin Packing (2002)
Csirik, Janos, Johnson, David S., Kenyon, Claire, Orlin, James B., Shor, Peter W., Weber, Richard R.
In this paper we present a theoretical analysis of the deterministic on-line {\em Sum of Squares} algorithm ($SS$) for bin packing introduced and studied experimentally in \cite{CJK99}, along with...
Circular Ones and Cyclic Staffing. (2002)
Orlin,James B., Ratliff,H. Donald
A large class of cyclic staffing problems, when formulated as (linear) integer programs, possess zero-one constraint matrices for which the ones in each row occur in consecutive components (the first...
Circular 1's and Cyclic Staffing. (2002)
Orlin,James B., Ratliff,H. Donald
A commonly encountered integer linear program, basic to cyclic staffing and scheduling, has a constraint matrix possessing the property of circular 1's in columns. In general, such a matrix is not...
A survey of very large-scale neighborhood search techniques (2002)
Ravindra K. Ahuja, Ravindra K. Ahuja, Krishna C. Jha, Krishna C. Jha, James B. Orlin, James B. Orlin, ...
The Quadratic Assignment Problem (QAP) consists of assigning n facilities to n locations so as to minimize the total weighted cost of interactions between facilities. The QAP arises in many diverse...
Minimum time and minimum cost path problems in street networks with periodic traffic lights (2002)
Ravindra K. Ahuja, James B. Orlin, Stefano Pallottino, Maria Grazia Scutellà
networks with periodic traffic lights
A very large scale neighborhood search algorithm for the quadratic assignment problem (2002)
Ravindra K. Ahuja, Ravindra K. Ahuja, Ozlem Ergun, Ozlem Ergun, James B. Orlin, James B. Orlin, ...
Many optimization problems of practical interest are computationally intractable. Therefore, a practical approach for solving such problems is to employ heuristic (approximation) algorithms that can...
A survey of very large-scale neighborhood search techniques (2002)
Many discrete optimization problems of practical interest cannot be solved to optimality in the available time. A practical approach to these problems is to use heuristic algorithms, which do not...
Ravindra K. Ahuja, Ravindra K. Ahuja, James B. Orlin, James B. Orlin
In this paper, we consider the problem of minimizing ∑ j j 1 j NC(x) ∈, subject to the following chain constraints l ≤ x 1 ≤ x 2 ≤ x 3 ≤ … ≤ x n ≤ u, where C j (x j) is a convex...
Ravindra K. Ahuja, Ravindra K. Ahuja, James 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 x 0 be a given...
Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem (2000)
Ravindra K. Ahuja, Ravindra K. Ahuja, James B. Orlin, James B. Orlin, Dushyant Sharma, Dushyant Sharma
The capacitated minimum spanning tree (CMST) problem is to find a minimum cost spanning tree with an additional cardinality constraint on the sizes of the subtrees incident to a given root node. The...
New polynomial-time cycle-canceling algorithms for minimum-cost flows,” in Networks (2000)
P. T. Sokkalingam, P. T. Sokkalingam, Ravindra K. Ahuja, Ravindra K. Ahuja, James B. Orlin, James B. Orlin
The cycle-canceling algorithm is one of the earliest algorithms to solve the minimum cost flow problem. This algorithm maintains a feasible solution x in the network G and proceeds by augmenting...
A faster algorithm for the inverse spanning tree problem (2000)
Ravindra K. Ahuja, Ravindra K. Ahuja, James B. Orlin, James B. Orlin
In this paper, we consider the inverse spanning tree problem. Given an undirected graph G 0 = (N 0, A 0) with n nodes, m arcs, an arc cost vector c, and a spanning tree T 0, the inverse spanning tree...
On the Sum-of-Squares Algorithm for Bin Packing (2000)
Janos Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
In this paper we present a theoretical analysis of the deterministic on-line Sum of Squares algorithm (SS) for bin packing, introduced and studied experimentally in [8], along with several new...
New polynomial-time cycle-canceling algorithms for minimum-cost flows,” in Networks (2000)
P. T. Sokkalingam, P. T. Sokkalingam, Ravindra K. Ahuja, Ravindra K. Ahuja, James B. Orlin, James B. Orlin
The cycle-canceling algorithm is one of the earliest algorithms to solve the minimum cost flow problem. This algorithm maintains a feasible solution x in the network G and proceeds by augmenting...
Solving the convex cost integer dual network flow problem (1999)
Ravindra K. Ahuja, Ravindra K. Ahuja, Dorit S. Hochbaum, Dorit S. Hochbaum, James B. Orlin, James B. Orlin
In this paper, we consider an integer convex optimization problem where the objective function is the sum of separable convex functions (that is, of the form Σ (i,j)∈Q F(w ij ij)+ Σi∈P i i 1 B...
Algorithms for the simple equal flow problem (1999)
Ravindra K. Ahuja, Ravindra K. Ahuja, James B. Orlin, James B. Orlin, Giovanni M. Sechi, Giovanni M. Sechi, ...
The minimum cost flow problem is to determine a least cost shipment of a commodity through a network G = (N, A) in order to satisfy demands at certain nodes from available supplies at other nodes. In...
OF TECHNOLOG Y Optimal Rounding of Instantaneous Fractional Flows Over Time (1999)
Lisa K. Fleischer, James B. Orlin
A transshipment problem with demands that exceed network capacity can be solved by sending flow in several waves. How can this be done in the minimum number, T, of waves, and at minimum cost, if...
Faster Algorithms for the Shortest Path Problem, (1998)
Ahuja, Ravindra K., Mehlhorn, Kurt, Orlin, James B., Tarjan, Robert E.
This document investigates efficient implementations of Dijkstra's shortest path algorithm. The authors propose a new data structure, called the redistributive heap, for use in this algorithm. On a...
Finding Minimum-Cost Flows by Double Scaling, (1998)
Ahuja, Ravindra K., Goldberg, Andrew V., Orlin, James B., Tarjan, Robert E.
Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm...
New Directions in Network Flows. (1998)
A new, fast algorithm has been developed for the solution of problems using Lagrangian relaxation. this algorithm appears to improve running times by a factor of n-squared, where n is the number of...
Polynomial Dual Network Simplex Algorithms, (1998)
Orlin, James B., Plotkin, Serge A., Tardos, Eva
We show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule. Our best pivoting strategy...
Combinatorial algorithms for inverse network flow problems (1998)
Ravindra K. Ahuja, Ravindra K. Ahuja, James B. Orlin, James B. Orlin
Diagnosing infeasibilities in network flow problems (1998)
Charu C. Aggarwal, Charu C. Aggarwal, Ravindra K. Ahuja, Ravindra K. Ahuja, Jianxiu Hao, Jianxiu Hao, ...
We consider the problem of finding a feasible flow in a directed G = (N, A) in which each node i ∈ N has a supply b(i), and each arc (i, j) ∈ A has a zero lower bound on flow and an upper bound u...
Combinatorial algorithms for inverse network flow problems (1998)
Ravindra K. Ahuja, Ravindra K. Ahuja, Ravindra K. Ahuja, James B. Orlin, James B. Orlin, James B. Orlin
An inverse optimization problems is defined as follows: Let S denote the set of feasible solutions of an optimization problem P, let c be a specified cost vector, and xO be a given feasible solution....
Ravindra K. Ahuja, Ravindra K. Ahuja, Ravindra K. Ahuja, James B. Orlin, James B. Orlin, James B. Orlin
In this paper, we consider the bipartite node weighted matching problem on a special class of graphs, called path graphs, and develop a highly efficient algorithm for solving it. This matching...
Linear Programming and General Problem (1998)
Ravindra K. Ahuja, James B. Orlin, Ravindra K. Ahuja, James B. Orlin, Ravindra K. Ahuja, 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 x 0 be a given...
A polynomial time primal network simplex algorithm for minimum cost flows (1997)
James B. Orlin, James B. Orlin, James B. Orlin
Developing a polynomial time algorithm for the minimum cost flow problem has been a long standing open problem. In this paper, we develop one such algorithm that runs in O(min(n 2 m log nC, n 2 m 2...
James B. Orlin, Donald Goldfarb, Donald Goldfarb, Zhiying Jin, Zhiying Jin, James B. Orlint
This paper presents two new combinatorial algorithms for the generalized circulation problem. After an initial step in which all flow-generating cycles are canceled and excesses are created, both...
Computational investigation of maximum flow algorithms (1997)
Ravindra K. Ahuja, Ravindra K. Ahuja, Murali Kodialam, Murali Kodialam, Ajay K. Mishra, Ajay K. Mishra, ...
The maximum flow algorithm is distinguished by the long line of successive contributions researchers have made in obtaining algorithms with incrementally better worst-case complexity. Some, but not...
A Faster Primal Network Simplex Algorithm (1996)
C. Aggarwal, H. Kaplan, J. Orlin, R. Tarjan, Charu C. Aggarwal, James B. Orlin
A faster primal network simplex algorithm
Use of representative operation counts in computational testing of algorithms (1996)
Ravindra K. Ahuja, Ravindra K. Ahuja, Ravindra K Ahuja, James B. Orlin, James B. Orlin, James B. Orlin, ...
The purpose of mathematical programming is insight, not numbers.
Inverse spanning tree problems : formulations and algorithms (1996)
Sokkalingam, P. T., Ahuja, Ravindra K., Orlin, James B.
Cover title.
Fast approximation schemes for multi-criteria combinatorial optimization (1995)
Hershel M. Safer, James B. Orlin
The solution to an instance of the standard Shortest Path problem is a single shortest route in a directed graph. Suppose, however, that each arc has both a distance and a cost, and that one would...
Fast approximation schemes for multi-criteria combinatorial optimization (1995)
Genome Therapeutics Corp, Hershel M. Safer, Hershel M. Safer, James B. Orlin, James B. Orlin
The solution to an instance of the standard Shortest Path problem is a single shortest route in a directed graph. Suppose, however, that each arc has both a distance and a cost, and that one would...
Abstract Optimized Crossover for the Independent Set Problem (1995)
Charu C. Aggarwal, James B. Orlin, Ray P. Tai, Charu C. Aggarwal, James B. Orlin, Ray P. Tai
We propose a knowledge-based crossover mechanism for genetic algorithms that exploits the structure of the solution rather than its coding. More generally, we suggest broad guidelines for...
Fast approximation schemes for multi-criteria combinatorial optimization (1995)
Genome Therapeutics Corp, Hershel M. Safer, Hershel M. Safer, Hershel M. Safer, James B. Orlin, James B. Orlin, ...
The solution to an instance of the standard Shortest Path problem is a single shortest route in a directed graph. Suppose, however, that each arc has both a distance and a cost, and that one would...
Applications of Network Optimization (1995)
Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin, M.R. Reddy
Network optimization has always been a core problem domain in operations research, as well as in computer science, applied mathematics, and many fields of engineering and management. Network...
Applications of Network Optimization (1995)
R. Ahuja, T. L. Magnanti, J. B. Orlin, Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin, ...
I
Fast approximation schemes for multi-criteria combinatorial optimization (1995)
Genome Therapeutics Corp, Hershel M. Safer, Hershel M. Safer, Hershel M. Safer, James B. Orlin, James B. Orlin, ...
The solution to an instance of the standard Shortest Path problem is a single shortest route in a directed graph. Suppose, however, that each arc has both a distance and a cost, and that one would...
Improved Algorithms For Bipartite Network Flow (1994)
Ravindra K. Ahuja, James B. Orlin, Clifford Stein, Robert E. Tarjan, Robert E
. In this paper, we study network flow algorithms for bipartite networks. A network G = (V; E) is called bipartite if its vertex set V can be partitioned into two subsets V 1 and V 2 such that all...
A technique for speeding up the solution of the Lagrangean dual (1994)
Dimitris Bertsimas, James B. Orlin
A technique for speeding up the solution of the Lagrangean rithm. dual
A technique for speeding up the solution of the Lagrangean dual (1994)
Dimitris Bertsimas, James B. Orlin
A technique for speeding up the solution of the Lagrangean rithm. dual
Abstract Diagnosing Infeasibilities in Network Flow Problems (1994)
Charu C. Aggarwal, Jianxiu Hao, James B. Orlin, Charu C. Aggarwal, Jianxiu Hao, James B. Orlin
We consider the problem of finding a feasible flow in which each node i has a supply b(i), and each arc has a lower bound of 0 on flow and an upper bound uij. It is well known that this feasibility...
Analysis of path-based approaches to genomic physical mapping (1994)
Rimm-Kaufman, Alan., Orlin, James B.
"November 1994, revised December 1994."
Determination of optimal vertices from feasible solutions in unimodular linear programming (1993)
Saigal, Romesh, Mizuno, Shinji, Orlin, James B.
In this paper we consider a linear programming problem with the underlying matrix unimodular, and the other data integer. Given arbitrary near optimum feasible solutions to the primal and the dual...
Finding minimum cost to time ratio cycles with small integral transit times (1993)
Let D = (V, E) be a digraph with n vertices and m arcs. For each e E E there is an associated cost ce and a transit time te; Ce can be arbitrary, but we require t to be a non-negative integer. The...
Quickmatch: A very fast algorithm for the assignment problem (1993)
In this paper, we consider the linear assignment problem defined on a bipartite network G = (r U I, A). The problem may be described as assigning each person in a set UT to a set V of tasks so as to...
A Parametric Worst Case Analysis for a Machine Scheduling Problem (1993)
Paul Mireault, Rakesh Vohra, James B. Orlin, Paul Mireault, James B. Orlin, Rakesh V. Vohra
We consider the problem of minimizing the makespan when scheduling tasks on two uniform parallel machines, where one machine is q times as efficient on each task as is the other. We compute the...
)1993 Kluwer Academic Publishers B.V. On Very Large Scale Assignment Problems (1993)
W. W. Hager, D. W. Hearn, P. M. Pardalos, Yusin Lee, James B. Orlin
In this paper we present computational testing results on very large scale random assignment problems. We consider a fully dense assignment problem with 2n nodes. Some conjectured or derived...
The Origin-Destination Shortest Path Problem (1992)
Muralidharan S. Kodialam, James B. Orlin, Muralidharan S. Kodialam, James B. Orlin
l-L--·--·mF·aPPII-t311-)-9- C _--i ·--- '--- U ·-- Ill-e--·------I _ I i..--.
I-----·r-·---^r^----- ·-------- (1992)
James B. Orlin, Clifford Stein
Parallel algorithms for the assignment and minimum-cost flow problems
Finding Minimum-Cost Flows by Double Scaling (1992)
Ravindra K. Ahuja, Ravindra K. Ahuja, Ravindra K. Ahuja, Andrew V. Goldberg, Andrew V. Goldberg, Andrew V. Goldberg, ...
Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm...
We consider the problem of finding the minimum capacity cut in a directed network G with n nodes. This problem has applications to network reliability and survivability and is useful in subroutines...
- ^;___·erca A FASTER STRONGLY POLYNOMIAL MINIMUM COST FLOW ALGORITHM (1991)
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...
Single transferable vote resists strategic voting (1991)
John J. Bartholdi, James B. Orlin
We give evidence that Single Tranferable Vote (STV) is computation-ally resistant to manipulation: It is NP-complete to determine whether there exists a (possibly insincere) preference that will...
Users And Customizable Software: A Co-Adaptive Phenomenon (1990)
James B. Orlin, Wendy E. Mackay, Wendy E. Mackay
Co-adaptive phenomena are defined as those in which the environment affects human behavior and at the same time, human behavior affects the environment. Such phenomena pose theoretical and...
Faster Algorithms for the Shortest Path Problem (1990)
Ravindra K. Ahuja, Kurt Mehlhorn, James B. Orlin, Robert E. Tarjan
Abstract. 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...
Faster algorithms for the shortest path problem (1990)
Ahuja, Ravindra K., Mehlhorn, Kurt, Orlin, James B., Tarjan, Robert E.
Determination of optimal vertices from feasible solutions in unimodular linear programming (1990)
Mizuno, Shinji., Saigal, Romesh, Orlin, James B.
"December, 1990."
Single transferable vote resists strategic voting (1990)
Bartholdi, J. J., Orlin, James B.
"November, 1990."
A Fast and Simple Algorithm for the Maximum Flow Problem (1989)
We present a simple sequential algorithm for the maximum flow problem on a network with n nodes, m arcs, and integer arc capacities bounded by U. Under the practical assumption that U is polynomially...
The theory of cyclic transfers (1989)
Paul M. Thompson, Paul M. Thompson, James B. Orlin, James B. Orlin
This paper develops the theory of cyclic transfers, a neighborhood search strategy for a broad class of combinatorial problems. The problem class is characterized by a two-phase decision process:...
A Faster Strongly Polynomial Minimum Cost Flow Algorithm (1988)
We present a new strongly polynomial 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...
Improved Time Bounds for the Maximum Flow Problem (1988)
X A Er, X Xaf X, Ravindra K. Ahuja, James B. Orlin, Robert E. Tarjan, Ravindra K. Ahuja, ...
tT~~~~~~~~ ~-.- it _.r)-1.--::- I:I
Faster Algorithms for the Shortest Path Problem (1988)
Ahuja, Ravindra K., Mehlhorn, Kurt, Orlin, James B., Tarjan, Robert E.
Faster Algorithms for the Shortest Path Problem (1988)
Ahuja, Ravindra K., Mehlhorn, Kurt, Orlin, James B., Tarjan, Robert E.
A fast and simple algorithm for the maximum flow problem (1988)
Ahuja, Ravindra K., Orlin, James B.
"June 1987, revised: March 1988."
Improved time bounds for the maximum flow problem (1988)
Ahuja, Ravindra K., Orlin, James B., Tarjan, Robert E.
"December 1987, revised June 1988."
Ahuja, Ravindra K., Orlin, James B.
"November 1988."
Ahuja, Ravindra K., Magnanti, Thomas L., Orlin, James B.
"August 1988. Revised: December, 1988."
North-Holland Recognizing hidden bicircular networks (1987)
Randy Shull, Alan Shuchat, James B. Orlin
Shull, R., A. Shuchat, J.B. Orlin and M. Lepp, Recognizing hidden bicircular networks, Discrete Applied Mathematics 41 (1993) 13-53. In this and a subsequent paper (by R. Shull, A. Shuchat, J.B....
The Complexity of Dynamic/Periodic Languages and Optimization Problems (1985)
2 Deterministic dynamic/periodic optimization problems arise naturally in various quantitative disciplines including Computer Science, Economics, and Operations Research. These periodic models may be...
Analysis and solution algorithms of sealift routing and scheduling problems : final report (1985)
Psaraftis, Harilaos N., Orlin, James B., Bienstock, Daniel, Thompson, Paul M.
Genuinely polynomial simplex and non-simplex algorithms for the minimum cost flow problem (1984)
"December 1984."
Fast algorithms for bin packing (1974)
Janos Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
In this paper we present a theoretical analysis of the online Sum-of-Squares algorithm (SS) for bin packing along with several new variants. SS is applicable to any instance of bin packing in which...
Fast algorithms for bin packing (1974)
Janos Csirik, David S. Johnson, Claire Kenyon, James B. Orlin, Peter W. Shor, Richard R. Weber
In this paper we present a theoretical analysis of the on-line Sum-of-Squares algorithm (SS) for bin packing along with several new variants. SS is applicable to any instance of bin packing in which...
Maximum Flow and Parametric Maximum Flow Problems (1908)
J. B. Orlin, R. K. Ahuja, James B. Orlin, Ravindra K. Ahuja
for
Genuinely Polynominal Simplex and Non-Simplex Algorithms for the Minimum Cost Flow Problem (1615)
We consider the minimum cost network flow problem min(cx: Ax=b, x> 0) on a graph G = (V,E). First we give a minor modification of Edmonds-Karp scaling technique, and we show that it solves the...
Approximate Local Search in Combinatorial Optimization
Orlin, James B., Punnen, Abraham P., Schulz, Andreas S.
Local search algorithms for combinatorial optimization problems are in general of pseudopolynomial running time and polynomial-time algorithms are often not known for finding locally optimal...
Computational investigations of maximum flow algorithms
Ahuja, Ravindra K., Kodialam, Murali, Mishra, Ajay K., Orlin, James B.
We provide two different neighborhood construction techniques for creating exponentially large neighborhoods that are searchable in polynomial time using dynamic programming. We illustrate both of...
Exact and Heuristic Methods for the Weapon Target Assignment Problem
Ahuja, Ravindra K., Kumar, Arvind, Jha, Krishna, Orlin, James B.
The Weapon Target Assignment (WTA) problem is a fundamental problem arising in defense-related applications of operations research. This problem consists of optimally assigning n weapons to m targets...
Ramaswamy, Ramkumar, Orlin, James B., Chakravarty, Nilopal
This paper addresses sensitivity analysis questions concerning the shortest path problem and the maximum capacity path problem in an undirected network. For both problems, we determine the maximum...