Submodular linear programs on forests


Faigle, Ulrich and Kern, Walter (1996) Submodular linear programs on forests. Mathematical programming, 72 (2). pp. 195-206. ISSN 0025-5610

open access
Abstract:A general linear programming model for an order-theoretic analysis of both Edmonds' greedy algorithm for matroids and the NW-corner rule for transportation problems with Monge costs is introduced. This approach includes the model of Queyranne, Spieksma and Tardella (1993) as a special case. We solve the problem by optimal greedy algorithms for rooted forests as underlying structures. Other solvable cases are also discussed.
Item Type:Article
Copyright:© 1996 Springer
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 140768