-
Article
Use of dynamic trees in a network simplex algorithm for the maximum flow problem
Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n 2 m) time. In this paper ...
-
Article
Finding minimum-cost flows by double scaling
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 running in O(nm(l...
-
Chapter and Conference Paper
Optimization algorithms for large networks
-
Article
Tight bounds on the number of minimum-mean cycle cancellations and related results
We prove a tight Θ(min(nm log(nC), nm2)) bound on the number of iterations of the minimum-mean cycle-canceling algorithm of Goldberg and Tarjan [13]. We do this by giving the lower bound and by improving the stro...
-
Chapter and Conference Paper
On implementing push-relabel method for the maximum flow problem
We study efficient implementations of the push-relabel method for the maximum flow problem. The resulting codes are faster than the previous codes, and much faster on some problem families. The speedup is due ...
-
Chapter and Conference Paper
Maximum skew-symmetric flows
We introduce the maximum skew-symmetric flow problem which generalizes flow and matching problems. We develop a theory of skew-symmetric flows that is parallel to the classical flow theory. We use the newly de...
-
Article
An efficient cost scaling algorithm for the assignment problem
The cost scaling push-relabel method has been shown to be efficient for solving minimum-cost flow problems. In this paper we apply the method to the assignment problem and investigate implementations of the me...
-
Chapter and Conference Paper
Negative-cycle detection algorithms
We study the problem of finding a negative length cycle in a network. An algorithm for the negative cycle problem combines a shortest path algorithm and a cycle detection strategy. We study various combination...
-
Article
Shortest paths algorithms: Theory and experimental evaluation
We conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. We also suggest new algorithms motivated by the experimental results and prove interesting theor...
-
Article
Path problems in skew-symmetric graphs
We study path problems in skew-symmetric graphs. These problems generalize the standard graph reachability and shortest path problems. We establish combinatorial solvability criteria and duality relations for ...
-
Chapter and Conference Paper
Implementations of Dijkstra’s Algorithm Based on Multi-Level Buckets
A 2-level bucket data structure [6] has been shown to perform well in a Dijkstra’s algorithm implementation [4]. In this paper we study how the implementation performance depends on the number of bucket levels...
-
Chapter and Conference Paper
Recent developments in maximum flow algorithms
-
Chapter and Conference Paper
An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow
The minimum-cost multicommodity flow problem involves si- multaneously ship** multiple commodities through a single network so that the total flow obeys arc capacity constraints and has minimum cost. Multicommo...
-
Chapter and Conference Paper
Selecting Problems for Algorithm Evaluation
In this paper we address the issue of develo** test sets for computational evaluation of algorithms. We discuss both test families for comparing several algorithms and selecting one to use in an application,...
-
Article
Negative-cycle detection algorithms
-
Chapter and Conference Paper
A Simple Shortest Path Algorithm with Linear Average Time
We present a simple shortest path algorithm. If the input lengths are positive and uniformly distributed, the algorithm runs in linear time. The worst-case running time of the algorithm is O(m + n log C), where n
-
Chapter and Conference Paper
Competitive Auctions for Multiple Digital Goods
Competitive auctions encourage consumers to bid their utility values while achieving revenue close to that of fixed pricing with perfect market analysis. These auctions were introduced in [6] in the context of se...
-
Chapter and Conference Paper
Shortest Path Algorithms: Engineering Aspects
We review shortest path algorithms based on the multi-level bucket data structure [6] and discuss the interplayb etween theorya nd engineering choices that leads to efficient implementations. Our experimental res...
-
Chapter and Conference Paper
Truthful and Competitive Double Auctions
In this paper we consider the problem of designing a mechanism for double auctions where bidders each bid to buy or sell one unit of a single commodity. We assume that each bidder’s utility value for the item ...
-
Chapter and Conference Paper
A Lower Bound on the Competitive Ratio of Truthful Auctions
We study a class of single-round, sealed-bid auctions for a set of identical items. We adopt the worst case competitive framework defined by [6,3] that compares the profit of an auction to that of an optimal s...
