A faster capacity scaling algorithm for minimum cost submodular flow |
| |
Authors: | Lisa Fleischer Satoru Iwata S Thomas McCormick |
| |
Institution: | (1) Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA 15213, USA, e-mail: lkf@andrew.cmu.edu, US;(2) Graduate School of Information Science and Technology, University of Tokyo, Tokyo 113-0033, Japan, e-mail: iwata@sr3.t.u-tokyo.ac.jp, JP;(3) Faculty of Commerce and Business Administration, University of British Columbia, Vancouver, BC V6T 1Z2 Canada, e-mail: stmv@adk.commerce.ubc.ca, CA |
| |
Abstract: | We describe an O(n
4
hmin{logU,n
2logn}) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds–Karp
capacity scaling algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails
scaling a relaxation parameter δ. Capacities are relaxed by attaching a complete directed graph with uniform arc capacity
δ in each scaling phase. We then modify a feasible submodular flow by relaxing the submodular constraints, so that complementary
slackness is satisfied. This creates discrepancies between the boundary of the flow and the base polyhedron of a relaxed submodular
function. To reduce these discrepancies, we use a variant of the successive shortest path algorithm that augments flow along
minimum cost paths of residual capacity at least δ. The shortest augmenting path subroutine we use is a variant of Dijkstra’s
algorithm modified to handle exchange capacity arcs efficiently. The result is a weakly polynomial time algorithm whose running
time is better than any existing submodular flow algorithm when U is small and C is big. We also show how to use maximum mean cuts to make the algorithm strongly polynomial. The resulting algorithm is the
first capacity scaling algorithm to match the current best strongly polynomial bound for submodular flow.
Received: August 6, 1999 / Accepted: July 2001?Published online October 2, 2001 |
| |
Keywords: | : submodular function – network flow – scaling algorithm Mathematics Subject Classification (1991): 90C27 |
本文献已被 SpringerLink 等数据库收录! |
|