Structures of polyhedra determined by submodular functions on crossing families

DOI10.1007/BF02592217MaRDI QIDQ3337243zbMATHOpenAlexFDO

Authors 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) Deterministic network models in operations research (90B10) Integer programming (90C10) Polytopes and polyhedra (52Bxx)

Recommendations

• Optimization over the polyhedron determined by a submodular function on a co-intersecting family
• Structural theorems for submodular functions, polymatroids and polymatroid intersections
• scientific article; zbMATH DE number 1953186
• scientific article; zbMATH DE number 1379520
• Polyhedral structure of submodular and posi-modular systems
• scientific article; zbMATH DE number 1303026
• On structures of bisubmodular polyhedra
• scientific article; zbMATH DE number 1342137
• Lattice polyhedra and submodular flows
• scientific article; zbMATH DE number 437545

Cites work

• scientific article; zbMATH DE number 3644825 (Why is no real title available?)
• scientific article; zbMATH DE number 3744939 (Why is no real title available?)
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A PRIMAL APPROACH TO THE INDEPENDENT ASSIGNMENT PROBLEM
• ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
• AN ALGORITHM FOR FINDING AN OPTIMAL INDEPENDENT LINKAGE
• An Algorithm for Submodular Functions on Graphs
• Computing Maximal “Polymatroidal” Network Flows
• Minimization of Some Nonlinear Functions over Polymatroidal Network Flows
• Minimization on submodular flows

Cited in

(29)

• Structural theorems for submodular functions, polymatroids and polymatroid intersections
• Combined connectivity augmentation and orientation problems
• A note on Frank's generalized polymatroids
• Duality for balanced submodular flows
• Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
• A CHARACTERIZATION OF FACES OF THE BASE POLYHEDRON ASSOCIATED WITH A SUBMODULAR SYSTEM
• On Packing Dijoins in Digraphs and Weighted Digraphs
• A capacity scaling algorithm for convex cost submodular flows
• On the orientation of graphs and hypergraphs
• Directed submodularity, ditroids and directed submodular flows
• Polyhedral structure of submodular and posi-modular systems
• A vector exchange property of submodular systems
• A Survey on Covering Supermodular Functions
• scientific article; zbMATH DE number 437545 (Why is no real title available?)
• An out-of-kilter method for submodular flows
• A decomposition of distributive lattices
• Decreasing minimization on M-convex sets: algorithms and applications
• scientific article; zbMATH DE number 1342137 (Why is no real title available?)
• On the subdifferential of a submodular function
• Generalized polymatroids and submodular flows
• Linear and combinatorial sharing problems
• Lattice polyhedra and submodular flows
• Submodular systems and related topics
• Sharing problems
• Optimization over the polyhedron determined by a submodular function on a co-intersecting family
• A note on the Frank-Tardos bi-truncation algorithm for crossing- submodular functions
• Edge splitting and connectivity augmentation in directed hypergraphs.
• Tree-compositions and orientations
• Fair integral submodular flows

This page was built for publication: Structures of polyhedra determined by submodular functions on crossing families

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