ZIB

Treffer pro Seite

Treffer 1 - 1 | 1 Treffer

Sortierung

Digitale Medien

Polynomial dual network simplex algorithms (1993)

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

Springer

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

zur Merkliste hinzufügen auf der Merkliste

Details

ISSN: 1436-4646

Schlagwort(e): Strongly polynomial ; dual simplex algorithm ; network simplex algorithm ; minimum cost network flows

Quelle: Springer Online Journal Archives 1860-2000

Thema: Informatik , Mathematik

Notizen: 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.

Materialart: Digitale Medien

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

Permalink

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

Artikel (Nationallizenzen)

Volltext

Treffer 1 - 1 | 1 Treffer