A cost-scaling algorithm for \(0-1\) submodular flows

DOI10.1016/S0166-218X(96)00011-XzbMath0872.90036MaRDI QIDQ678855

Maiko Shigeno, Satoru Iwata

Publication date: 27 April 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

greedy algorithmauction-like methodcost-scaling algorithmcost-splittingminimum cost 0-1 submodular flowssuccessive-shortest-path method

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Boolean programming (90C09)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding feasible vectors of Edmonds-Giles polyhedra
• Generalized polymatroids and submodular flows
• Minimization on submodular flows
• A note on the Frank-Tardos bi-truncation algorithm for crossing- submodular functions
• New scaling algorithms for the assignment and minimum mean cycle problems
• Submodular functions and optimization.
• Faster Scaling Algorithms for Network Problems
• An Algorithm for Submodular Functions on Graphs
• AN EFFICIENT COST SCALING ALGORITHM FOR THE INDEPENDENT ASSIGNMENT PROBLEM

This page was built for publication: A cost-scaling algorithm for \(0-1\) submodular flows