caa a22 4500 47576952X CHVBK 20180406123615.0 cr unu---uuuuu 170329e20000601xx s 000 0 eng 10.1007/s101070050013 doi (NATIONALLICENCE)springer-10.1007/s101070050013 Fujishige Satoru Division of Systems Science, Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka 560-8531 Japan, e-mail: fujishig@sys.es.osaka-u.ac.jp, JP aut A note on Faigle and Kern's dual greedy polyhedra [Elektronische Daten] [Satoru Fujishige] 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. Springer-Verlag Berlin Heidelberg, 2000 Key words: greedy algorithm - poset - antichain - submodular function - submodular flow nationallicence https://doi.org/10.1007/s101070050013 text/html Onlinezugriff via DOI 1 brief-communication jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s101070050013 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Fujishige Satoru Division of Systems Science, Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka 560-8531 Japan, e-mail: fujishig@sys.es.osaka-u.ac.jp, JP aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer