A new strongly polynomial dual network simplex algorithm

A new strongly polynomial dual network simplex algorithm

0.00 Avg rating—0 Votes
Article ID: iaor1999858
Country: Netherlands
Volume: 78
Issue: 2
Start Page Number: 131
End Page Number: 148
Publication Date: Aug 1997
Journal: Mathematical Programming
Authors: ,
Keywords: networks
Abstract:

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' dual network simplex algorithm by a factor of m/n.

Reviews

Required fields are marked *. Your email address will not be published.