@inproceedings{e76d30e26e1940cb8fabc55c9f018522,

title = "Finding minimum-cost circulations by canceling negative cycles",

abstract = "A classical algorithm for finding a minimum-cost circulation consists of repeatedly finding a residual cycle of negative; cost and canceling it by pushing enough flow around the cycle to saturate an arc. We show that a judicious choice of cycles for canceling leads to a polynomial bound on the number of iterations in this algorithm. This gives a very simple strongly polynomial algorithm that uses no scaling. A variant of the algorithm that uses dynamic trees runs in O(nm(log n) mini{log(nC), m log n}) time on a network of n vertices, m arcs, and arc costs of maximum absolute value C. This bound is comparable to those of the fastest previously known algorithms.",

author = "Goldberg, {Andrew V.} and Tarjan, {Robert Endre}",

year = "1988",

month = jan,

day = "1",

doi = "10.1145/62212.62250",

language = "English (US)",

isbn = "0897912640",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "388--397",

booktitle = "Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988",

note = "20th Annual ACM Symposium on Theory of Computing, STOC 1988 ; Conference date: 02-05-1988 Through 04-05-1988",

}