Submodular linear programs on forests

Share/Save/Bookmark

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

[img]
Preview
PDF
472Kb
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
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/79985
Official URL:http://dx.doi.org/10.1007/BF02592089
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 140768