A new strongly polynomial dual network simplex algorithm
Copyright policy )A new strongly polynomial dual network simplex algorithm
This paper presents a new dual network simplex algorithm for the minimum cost network flow problem. The algorithm works directly on the original capacitated network and runs in O(mn(m + n log n) log n) time for the network with n nodes and m arcs. This complexity is better than the complexity of Orlin, Plotkin and Tardos' (1993) dual network simplex algorithm by a factor of m/n..
- Autonomous University of Barcelona Spain
- St Petersburg University Russian Federation
- Rutgers, The State University of New Jersey United States
Dual simplex algorithm, dual network simplex algorithm, minimum cost network flow, Network simplex algorithm, Deterministic network models in operations research, Minimum cost network flow problem, Abstract computational complexity for mathematical programming problems
Dual simplex algorithm, dual network simplex algorithm, minimum cost network flow, Network simplex algorithm, Deterministic network models in operations research, Minimum cost network flow problem, Abstract computational complexity for mathematical programming problems
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).15 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!