ZIB

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

Polynomial dual network simplex algorithms (1993)

Orlin, James B. ; Plotkin, Serge A. ; Tardos, Éva

Springer

Mathematical programming 60 (1993), S. 255-276

add to mindlist on the mindlist

Details

ISSN: 1436-4646

Keywords: Strongly polynomial ; dual simplex algorithm ; network simplex algorithm ; minimum cost network flows

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: Abstract 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 leads to an O(m 2 logn) bound on the number of pivots, wheren andm denotes the number of nodes and arcs in the input network. If the demands are integral and at mostB, we also give an O(m(m+n logn) min(lognB, m logn))-time implementation of a strategy that requires somewhat more pivots.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF01580615

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit