A capacity scaling algorithm for M-convex submodular flow

DOI10.1007/s10107-004-0562-3zbMath1079.90112OpenAlexW2134750400MaRDI QIDQ1777220

Satoko Moriguchi, Kazuo Murota, Satoru Iwata

Publication date: 12 May 2005

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-004-0562-3

zbMATH Keywords

AlgorithmDiscrete optimizationDiscrete convex functionSubmodular flow

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

Ameso optimization: a relaxation of discrete midpoint convexity, M-Convex Function Minimization Under L1-Distance Constraint and Its Application to Dock Reallocation in Bike-Sharing System, Scaling, proximity, and optimization of integrally convex functions, The b‐bibranching problem: TDI system, packing, and discrete convexity, Discrete Midpoint Convexity, An efficient algorithm for minimizing M-convex functions under a color-induced budget constraint, Recent Developments in Discrete Convex Analysis, Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications, Competitive Equilibrium and Trading Networks: A Network Flow Approach

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Convexity and Steinitz's exchange property
• Finding feasible vectors of Edmonds-Giles polyhedra
• Submodular flow problem with a nonseparable cost function
• Submodular functions and optimization
• Valuated matroids
• New algorithms for the intersection problem of submodular systems
• Discrete convex analysis
• A capacity scaling algorithm for convex cost submodular flows
• Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
• Application of M-convex submodular flow problem to mathematical economics
• A faster capacity scaling algorithm for minimum cost submodular flow
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Capacity scaling algorithm for scalable M-convex submodular flow problems
• Solving the Convex Cost Integer Dual Network Flow Problem
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• A Primal-Dual Algorithm for Submodular Flows
• Layered Augmenting Path Algorithms
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
• Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
• Discrete Convex Analysis
• Minimizing a Convex Cost Closure Set
• A Faster Scaling Algorithm for Minimizing Submodular Functions
• Valuated Matroid Intersection I: Optimality Criteria
• Valuated Matroid Intersection II: Algorithms
• Conjugate Scaling Algorithm for Fenchel-Type Duality in Discrete Convex Optimization
• An efficient algorithm for image segmentation, Markov random fields and related problems