A fast cost scaling algorithm for submodular flow

DOI10.1016/S0020-0190(00)00052-1zbMATH Open1339.90325MaRDI QIDQ294751FDOQ294751

S. Thomas McCormick, Satoru Iwata, Maiko Shigeno

Publication date: 16 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019000000521?np=y

zbMATH Keywords

algorithmscomputational complexitycombinatorial optimizationnetwork flowsubmodular function

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Geometric algorithms and combinatorial optimization
• Scaling algorithms for network problems
• Finding Minimum-Cost Circulations by Successive Approximation
• A new approach to the maximum-flow problem
• Submodular functions and optimization
• An out-of-kilter method for submodular flows
• An application of simultaneous diophantine approximation in combinatorial optimization
• Generalized polymatroids and submodular flows
• Minimization on submodular flows
• A dual algorithm for submodular flow problems
• Finding minimum-cost flows by double scaling
• On the computational behavior of a polynomial-time network flow algorithm
• Negative circuits for flows and submodular flows
• New algorithms for the intersection problem of submodular systems
• A capacity scaling algorithm for convex cost submodular flows
• A faster capacity scaling algorithm for minimum cost submodular flow
• A polynomial cycle canceling algorithm for submodular flows
• A submodular network simplex method
• A Primal-Dual Algorithm for Submodular Flows
• Layered Augmenting Path Algorithms
• A PRIMAL ALGORITHM FOR THE SUBMODULAR FLOW PROBLEM WITH MINIMUM-MEAN CYCLE SELECTION
• A Strongly Polynomial Algorithm for Minimum Cost Submodular Flow Problems
• Minimum cost flow with set-constraints
• Computing Maximal “Polymatroidal” Network Flows
• ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
• Finding feasible vectors of Edmonds-Giles polyhedra

Cited In (7)

• Lattice polyhedra and submodular flows
• Minimizing a sum of submodular functions
• Title not available (Why is that?)
• The \(b\)-branching problem in digraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast cycle canceling algorithms for minimum cost submodular flow

This page was built for publication: A fast cost scaling algorithm for submodular flow

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294751)