Directed submodularity, ditroids and directed submodular flows

Directed submodularity, ditroids and directed submodular flows

0.00 Avg rating0 Votes
Article ID: iaor1988645
Country: Netherlands
Volume: 42
Issue: 3
Start Page Number: 579
End Page Number: 599
Publication Date: Dec 1988
Journal: Mathematical Programming
Authors:
Abstract:

Set relations and operations such as inclusion, union and intersection are generalized to directed subsets whose elements are distinguished between forward and backward elements. The concepts of submodular functions, matroids and polymatroidal network flows are extended to the concepts of directed submodular functions, ditroids and directed submodular flows on directed subsets. Two unrelated matroids (submodular functions) can be embedded in one ditroid (directed submodular function). Total dual integrality is preserved in these generalizations and proved for very general set-function class-directed odd submodular functions.

Reviews

Required fields are marked *. Your email address will not be published.