New algorithms for the intersection problem of submodular systems

DOI10.1007/BF03167272MaRDI QIDQ1202762zbMATH OpenOpenAlexFDO

Authors Satoru Fujishige, Xiaodong Zhang

Publication date 14 February 1993

Published in Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf03167272

zbMATH Keywords

intersection problemmaximum common subbasepreflow-push approachshortest augmenting pathssubmodular functionsubmodular systems

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• scientific article; zbMATH DE number 3922372
• Approximation algorithm and its performance for maximizing submodular function subject to matroid intersection
• Algorithms for submodular totally dual integral problems
• A Structure Theory for the Parametric Submodular Intersection Problem
• Exact algorithms for combinatorial optimization problems with submodular objective functions
• Polynomial-time algorithms for submodular Laplacian systems
• Algorithms for covering multiple submodular constraints and applications
• New approximations and hardness results for submodular partitioning problems
• Semi-streaming algorithms for submodular matroid intersection
• Semi-streaming algorithms for submodular matroid intersection

Cites work

• A new approach to the maximum-flow problem
• ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
• An out-of-kilter method for submodular flows
• Analysis of Preflow Push Algorithms for Maximum Network Flow
• Computing Maximal “Polymatroidal” Network Flows
• scientific article; zbMATH DE number 50766 (Why is no real title available?)
• Submodular functions and optimization
• Systems analysis by graphs and matroids. Structural solvability and controllability
• Use of matroid theory in operations research, circuits and systems theory

Cited in

(16)

• A push-relabel framework for submodular function minimization and applications to parametric optimization
• A capacity scaling algorithm for M-convex submodular flow
• Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
• Simple push-relabel algorithms for matroids and submodular flows
• A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem
• Separation of partition inequalities with terminals
• A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows
• A fast cost scaling algorithm for submodular flow
• A Structure Theory for the Parametric Submodular Intersection Problem
• A Fast Parametric Submodular Intersection Algorithm for Strong Map Sequences
• Discrete convex functions on graphs and their algorithmic applications
• Finding a stable allocation in polymatroid intersection
• Semi-streaming algorithms for submodular matroid intersection
• Semi-streaming algorithms for submodular matroid intersection
• Minimizing a sum of submodular functions
• Submodular function minimization

This page was built for publication: New algorithms for the intersection problem of submodular systems

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