登入選單
返回Google圖書搜尋
出版Laboratory for Computer Science, Massachusetts Inst. of Technology, 1987
URLhttp://books.google.com.hk/books?id=eIkrGwAACAAJ&hl=&source=gbs_api
註釋We develop a new approach to solving minimum cost circulation problems. Our approach combines methods for solving the maximum flow problems with successive approximation techniques based on cost scaling. We measure the accuracy of a solution by the amount that the complementary slackness conditions are violated. We propose a simple minimum cost circulation algorithm, one version of which runs in O(n3log(nC)) time on an n-vertex network with integer arc costs of absolute value at most C. By incorporating sophisticated data structures into the algorithm, we obtain a time bound of O(nmlog(n2/m)log(nC)) on a network with m arcs. A slightly different use of our approach shows that a minimum cost circulation can be computed by solving a sequence of O(nlog(nC)) blocking flow problems. A corollary of this result is an O(n2(logn)log(nC)-time, n-processor parallel minimum cost circulation algorithm. Our approach also yields strongly polynomial minimum cost circulation algorithms. Our results provide evidence that the minimum cost circulation problem is not much harder than the maximum flow problem. We believe that a suitable implementation of our method will perform extremely well in practice. Keywords: Network flows, Minimum cost flow, Combinatorial optimization.