Article ID: | iaor20013546 |
Country: | Germany |
Volume: | 88 |
Issue: | 1 |
Start Page Number: | 217 |
End Page Number: | 220 |
Publication Date: | Jan 2000 |
Journal: | Mathematical Programming |
Authors: | Fujishige Satoru |
Keywords: | polyhedra |
U. Faigle and W. Kern have recently extended the work of their earlier paper and of M. Queyranne, F. Spieksma and F. Tardella and have shown that a dual greedy algorithm works for a system of linear inequalities with {0,1}-coefficients defined in terms of antichains of an underlying poset and a submodular function on the set of ideals of the poset under some additional condition on the submodular function. In this note we show that Faigle and Kern's dual greedy polyhedra belong to a class of submodular flow polyhedra, i.e., Faigle and Kern's problem is a special case of the submodular flow problem that can easily be solved by their greedy algorithm.