Dual coordinate step methods for linear network flow problems (Q1115790)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Dual coordinate step methods for linear network flow problems
scientific article

    Statements

    Dual coordinate step methods for linear network flow problems (English)
    0 references
    0 references
    0 references
    0 references
    1988
    0 references
    We review a class of recently-proposed linear-cost network flow methods which are amenable to distributed implementation. All the methods in the class use the notion of \(\epsilon\)-complementary slackness, and most do not explicitly manipulate any ``global'' objects such as paths, trees, or cuts. Interestingly, these methods have stimulated a large number of new serial computational complexity results. We develop the basic theory of these methods and present two specific methods, the \(\epsilon\)-relaxation algorithm for the minimum-cost flow problem, and the auction algorithm for the assignment problem. We show how to implement these methods with serial complexities of \(O(N^ 3\log NC)\) and O(NA log NC), respectively. We also discuss practical implementation issues and computational experience to date. Finally, we show how to implement \(\epsilon\)- relaxation in a completely asynchronous, ``chaotic'' environment in which some processors compute faster than others, some processors communicate faster than others, and there can be arbitrarily large communication delays.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    distributed algorithms
    0 references
    asynchronous algorithms
    0 references
    linear-cost network flow
    0 references
    \(\epsilon \) -complementary slackness
    0 references
    \(\epsilon \) -relaxation algorithm
    0 references
    minimum-cost flow
    0 references
    auction algorithm
    0 references
    assignment problem
    0 references
    serial complexities
    0 references
    computational experience
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references