Submodular linear programs on forests

U. Faigle, Walter Kern

Research output: Contribution to journalArticleAcademicpeer-review

17 Citations (Scopus)
108 Downloads (Pure)

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.
Original languageUndefined
Pages (from-to)195-206
Number of pages12
JournalMathematical programming
Volume72
Issue number2
DOIs
Publication statusPublished - 1996

Keywords

  • Greedy algorithm - Monge property - Submodular function - Ordered set - Disributive lattice
  • IR-79985
  • METIS-140768

Cite this