A note on Faigle and Kern's dual greedy polyhedra

A note on Faigle and Kern's dual greedy polyhedra

0.00 Avg rating0 Votes
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:
Keywords: polyhedra
Abstract:

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.

Reviews

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