Structures of polyhedra determined by submodular functions on crossing families

DOI10.1007/BF02592217zbMath0545.90097OpenAlexW2068241960MaRDI QIDQ3337243

Satoru Fujishige

Publication date: 1984

Published in: Mathematical Programming (Search for Journal in Brave)

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

zbMATH Keywords

submodular functiondistributive latticecrossing family of subsetsindependent flow problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Deterministic network models in operations research (90B10) Polytopes and polyhedra (52Bxx)

Related Items

Linear and combinatorial sharing problems, An out-of-kilter method for submodular flows, Sharing problems, A capacity scaling algorithm for convex cost submodular flows, Fair integral submodular flows, Generalized polymatroids and submodular flows, Optimization over the polyhedron determined by a submodular function on a co-intersecting family, Directed submodularity, ditroids and directed submodular flows, Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested, Lattice polyhedra and submodular flows, On Packing Dijoins in Digraphs and Weighted Digraphs, On the orientation of graphs and hypergraphs, Combined connectivity augmentation and orientation problems, A Survey on Covering Supermodular Functions, Edge splitting and connectivity augmentation in directed hypergraphs., Tree-compositions and orientations, A note on the Frank-Tardos bi-truncation algorithm for crossing- submodular functions, On the subdifferential of a submodular function, Duality for balanced submodular flows, A vector exchange property of submodular systems, Decreasing minimization on M-convex sets: algorithms and applications, A note on Frank's generalized polymatroids, A decomposition of distributive lattices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimization on submodular flows
• Minimization of Some Nonlinear Functions over Polymatroidal Network Flows
• Computing Maximal “Polymatroidal” Network Flows
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
• AN ALGORITHM FOR FINDING AN OPTIMAL INDEPENDENT LINKAGE
• A PRIMAL APPROACH TO THE INDEPENDENT ASSIGNMENT PROBLEM
• ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
• An Algorithm for Submodular Functions on Graphs