Flow Network Formulations of Polymatroid Optimization Problems

DOI10.1016/S0304-0208(08)72451-4MaRDI QIDQ4740302zbMATH OpenOpenAlexFDO

Authors Eugene L. Lawler, Chip Martel

Publication date 1982

Published in North-Holland Mathematics Studies (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-0208(08)72451-4

zbMATH Keywords

capacity constraintslinking systemsmatroid optimizationmax-flow min-cut theoremmin-max theorempolymatroid rank functionspolymatroidal network flow modelproblems of gammoids

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Deterministic network models in operations research (90B10) Integer programming (90C10) Programming involving graphs or networks (90C35)

Cited in

(6)

• Maximal dynamic polymatroid flows and applications
• Directed submodularity, ditroids and directed submodular flows
• Simple push-relabel algorithms for matroids and submodular flows
• Polymatroidal flows with lower bounds
• Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications
• Submodular hypergraph partitioning: metric relaxations and fast algorithms via an improved cut-matching game

This page was built for publication: Flow Network Formulations of Polymatroid Optimization Problems

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