SUBMODULAR LINEAR-PROGRAMS ON FORESTS

Authors
FAIGLE U KERN W
Citation
U. Faigle et W. Kern, SUBMODULAR LINEAR-PROGRAMS ON FORESTS, Mathematical programming, 72(2), 1996, pp. 195-206
Citations number
11
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming
Journal title
Mathematical programming → ACNP
ISSN journal
00255610
Volume
72
Issue
2
Year of publication
1996
Pages
195 - 206
Database
ISI
SICI code
0025-5610(1996)72:2<195:SLOF>2.0.ZU;2-A
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 sp ecial case. We solve the problem by optimal greedy algorithms for root ed forests as underlying structures. Other solvable cases are also dis cussed.