Submodular linear programs on forests

U. Faigle; Walter Kern

doi:10.1007/BF02592089

Submodular linear programs on forests

U. Faigle
, Walter Kern

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

17 Citations (Scopus)

325 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 language	Undefined
Pages (from-to)	195-206
Number of pages	12
Journal	Mathematical programming
Volume	72
Issue number	2
DOIs	https://doi.org/10.1007/BF02592089
Publication status	Published - 1996

Keywords

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

Access to Document

10.1007/BF02592089

Faigle96submodular

Cite this

@article{49f27d7a06ba4ac5abafe369f36f2e38,

title = "Submodular linear programs on forests",

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.",

keywords = "Greedy algorithm - Monge property - Submodular function - Ordered set - Disributive lattice, IR-79985, METIS-140768",

author = "U. Faigle and Walter Kern",

year = "1996",

doi = "10.1007/BF02592089",

language = "Undefined",

volume = "72",

pages = "195--206",

journal = "Mathematical programming",

issn = "0025-5610",

publisher = "Springer",

number = "2",

}

TY - JOUR

T1 - Submodular linear programs on forests

AU - Faigle, U.

AU - Kern, Walter

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

KW - Greedy algorithm - Monge property - Submodular function - Ordered set - Disributive lattice

KW - IR-79985

KW - METIS-140768

U2 - 10.1007/BF02592089

DO - 10.1007/BF02592089

M3 - Article

SN - 0025-5610

VL - 72

SP - 195

EP - 206

JO - Mathematical programming

JF - Mathematical programming

IS - 2

ER -