A general class of greedily solvable linear programs

M. Queyranne, F.C.R. Spieksma, F. Tardella

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

22 Citaten (Scopus)


A greedy algorithm solves a dual pair of linear programs where the primal variables are associated to the elements of a sublattice B of a finite product lattice, and the cost coefficients define a submodular function on B. This approach links and generalizes two well-known classes of greedily solvable linear programs. The primal problem generalizes the (ordinary and multi-index) transportation problems satisfying a Monge condition (Hoffman 1963; Bein et al. 1995) to the case of forbidden cells where the nonforbidden cells form a sublattice. The dual problem generalizes to an arbitrary finite product lattice the linear optimization problem over submodular polyhedra (Lovász 1983; Fujishige and Tomizawa 1983), which stemmed from the work of Edmonds (1970) on polymatroids. Our model and results also encompass the dual pairs of linear programs and their greedy solutions defined by Lovász (1983) for the special case of the Boolean algebra, and by Faigle and Kern (1996) for the case of so-called “rooted forests.” We also discuss relationships between Monge properties and submodularity, and present a class of problems with submodular costs arising in production and logistics.
Originele taal-2Engels
Pagina's (van-tot)892-908
TijdschriftMathematics of Operations Research
Nummer van het tijdschrift4
StatusGepubliceerd - nov 1998
Extern gepubliceerdJa

Citeer dit